Cod sursa(job #1208104)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 14 iulie 2014 19:05:17
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<fstream>
using namespace std;

struct cell
{
    int cost,cantitate;
};

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;
    bool test;
    fin>>n>>s>>t;
    fin>>a[1].cost>>a[1].cantitate;
    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;
            deque[++ul]=a[i];
            test=1;
            if (ul-pr>t) pr++;
            while (pr<ul && test)
                {
                    j=pr;l=j+1;
                    if (1LL*deque[j].cost*deque[ul].cantitate+1LL*(ul-j)*s*deque[ul].cantitate>1LL*deque[l].cost*deque[ul].cantitate+1LL*(ul-l)*s*deque[ul].cantitate)
                        pr++;
                    else test=0;
                }
            sum+=1LL*deque[pr].cost*deque[ul].cantitate+1LL*(ul-pr)*s*deque[ul].cantitate;
        }
    fout<<sum<<"\n";
    return 0;
}