Cod sursa(job #935939)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 5 aprilie 2013 09:47:50
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <iostream>
#include <iterator>
#include <deque>
#include <algorithm>

#define MAXN 100002

using namespace std;

int cost[MAXN];
int demand[MAXN];

int main()
{
    int n, t;
    long long s;
    fstream fin("branza.in", fstream::in);
    fstream fout("branza.out", fstream::out);
    
    fin >> n >> s >> t;
    //cout << n << " " << s << " " << t << endl;
    
    for (int i=0; i<n; ++i)
    {
        fin >> cost[i] >> demand[i];
        //cout << cost[i] << " " << demand[i] << endl;
    }
    
    long long totalCost = 0;
    deque<int> deqStore;
    
    for (int i=0; i<n; ++i)
    {
        while (!deqStore.empty() && cost[deqStore.back()] + (i - deqStore.back()) * s > cost[i])
        {
            deqStore.pop_back();
        }
        deqStore.push_back(i);
        
        if (deqStore.front() < i - t)
        {
            deqStore.pop_back();
        }
        
        //cout << (demand[i] * (cost[deqStore.front()] + (i - deqStore.front()) * s)) << endl;
        
        totalCost += (demand[i] * (cost[deqStore.front()] + (i - deqStore.front()) * s));
    }
    
    fout << totalCost << "\n";
    
    return 0;
}