Cod sursa(job #825248)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 27 noiembrie 2012 22:41:33
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");
int n,t,s;
long long cost[100001];
long long cant[100001];
	
int main(){
	
    f>>n>>s>>t;
    for(int i=0; i<n; ++i)
        f>>cost[i]>>cant[i];

    long long suma = 0;
    deque<long long> d;
    d.push_back(0);
	
    suma+=cant[0]*cost[0];
    for(int i=1; i<n; ++i){
		
        while(!d.empty() && cost[i]<cost[d.back()]+s*(i-d.back()))
            d.pop_back();
        d.push_back(i);
        while(i-d.front()>t)
			d.pop_front();
		
        suma+=cost[d.front()]*cant[i]+cant[i]*s*(i-d.front());
    }

    g<<suma;

    return 0;
}