Cod sursa(job #1208346)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 15 iulie 2014 14:31:37
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<fstream>
using namespace std;

struct cell
{
    int cost,cantitate;
    int poz;
};

ifstream fin("branza.in");
ofstream fout("branza.out");

const int NMAX=100005;

int n,s,t;
long long dp[NMAX];
cell a[NMAX];
cell deque[NMAX];
long long sum;

int main()
{
    int i,j,l,pr,ul,last;
    fin>>n>>s>>t;
    fin>>a[1].cost>>a[1].cantitate;
    a[1].poz=1;
    sum+=1LL*a[1].cost*a[1].cantitate;
    pr=ul=1;
    deque[1]=a[1];
    for (i=2;i<=n;i++)
        {
            fin>>a[i].cost>>a[i].cantitate;
            a[i].poz=i;
            while (ul>=pr && 1LL*a[i].cost*a[i].cantitate<1LL*deque[ul].cost*a[i].cantitate+1LL*(i-deque[ul].poz)*s*a[i].cantitate)
                ul--;
            deque[++ul]=a[i];
            if (deque[ul].poz-deque[pr].poz>t) pr++;
            sum+=1LL*deque[pr].cost*deque[ul].cantitate+1LL*(deque[ul].poz-deque[pr].poz)*s*deque[ul].cantitate;
        }
    fout<<sum<<"\n";
    return 0;
}