Cod sursa(job #2156812)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 9 martie 2018 00:23:17
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.49 kb
#include <fstream>
using namespace std;
#define ll long long
ifstream in("branza.in");
ofstream out("branza.out");
int a[5000001];
int d[5000001];
int main(){
    int n,k,p,st=0,dr=-1,i,j;
    in>>n>>p>>k;
    ll s=0,c;
    for(i=1; i<=n; ++i){
        in>>a[i]>>c;
        if(st<=dr && d[st]==i-k)
            ++st;
        while(st<=dr && a[i]<=a[d[dr]]+(i-d[dr])*p)
            --dr;
        d[++dr]=i;
        s+=(a[d[st]]+(i-d[st])*p)*c;
    }
    out<<s;
    return 0;
}