Cod sursa(job #1419076)

Utilizator robx12lnLinca Robert robx12ln Data 14 aprilie 2015 17:43:33
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<fstream>
#define f first
#define s second
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int d[100005];
unsigned long long c,u,p,k,i,n,cost;
pair<int,int> v[100005];
int main(){
    fin>>n>>c>>k;
    for(i=1;i<=n;i++){
        fin>>v[i].first>>v[i].second;
    }
    d[1]=p=u=1;
    cost=v[1].f*v[1].s;
    for(i=2;i<=n;i++){
        while(p<=u && v[d[u]].f+(i-d[u])*c*1LL > v[i].f){
            u--;
        }
        d[++u]=i;
        if(i-d[u]==k+1){
            p++;
        }
        cost+=(v[d[p]].f+(i-d[p])*c)*v[i].s*1LL;
    }
    fout<<cost;
    return 0;
}