Cod sursa(job #961156)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 18:01:21
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<fstream>
#include<deque>
using namespace std;
struct zi{
    long long pret, pos;
};
deque<zi> br;
int main(){
    ifstream in("branza.in");
    ofstream out("branza.out");
    long long n,s,t,cost=0,req; zi current;
    in>>n>>s>>t;
    for(int i=1; i<=n; i++){
        in>>current.pret>>req;
        current.pos=i;
        while(!br.empty()&&br.back().pret+s*(i-br.back().pos)>current.pret){
            br.pop_back();
        }
        while(!br.empty()&&i-br.front().pos>t){
            br.pop_front();
        }
        br.push_back(current);
        cost+=(br.front().pret+s*(i-br.front().pos))*req;
    }
    out<<cost<<"\n";
    return 0;
}