Cod sursa(job #1704680)

Utilizator Matei_IgnutaMatei Ignuta Matei_Ignuta Data 19 mai 2016 10:56:27
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
#include <queue>

#define f first
#define s second

using namespace std;

deque< pair<int,int> > d;
int cost,cant,n,s,t;
long long total;

int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);
    scanf("%d %d %d", &n, &s, &t);
    total=0LL;
    for(int i=1;i<=n;++i)
    {
       scanf("%d %d", &cost, &cant);
       if(d.front().s < i-t)
        d.pop_front();
       while( !d.empty() and cost <= (i-d.back().s) * s + d.back().f )
        d.pop_back();
       d.push_back( {cost,i} );
       total=total + 1LL + cant * ((i-d.front().s) * s + d.front().f);
    }
    printf("%d\n", total);
    return 0;
}