Cod sursa(job #850608)

Utilizator stoicatheoFlirk Navok stoicatheo Data 8 ianuarie 2013 17:24:12
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<fstream>
#define dim 100010
using namespace std;
 
ifstream f("branza.in");
ofstream g("branza.out");
 
int n,s,t,i,deque[dim],P[dim],C[dim];
long long D[dim],sum;
int main(){
     
    f>>n>>s>>t;
     
    for(i=1;i<=n;i++)
        f>>C[i]>>P[i];
     
    int p=1;
    int u=0;
     
    for(i=1;i<=n;i++){
        while(C[i]<(C[deque[u]]+(i-deque[u])*s)&&u>=p)
            u--;
        deque[++u]=i;
        if(deque[p]<(i-t))
            p++;
        D[i]=C[deque[p]]+(i-deque[p])*s;
    }
     
    for(i=1;i<=n;i++)
        sum+=D[i]*P[i];
     
    g<<sum;
     
    return 0;
}