Cod sursa(job #2159397)

Utilizator amarghescuAnton Marghescu amarghescu Data 10 martie 2018 22:00:42
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<cstdio>
#include<algorithm>
using namespace std;
#define c first
#define p second
long long st[100005];
pair<long long,long long>v[100005];
int main(){
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
long long n,s,t,i,sz,lef,rasp=0;
scanf("%lld%lld%lld",&n,&s,&t);
for(i=1;i<=n;i++)
scanf("%lld%lld",&v[i].c,&v[i].p);
sz=0;
lef=1;
for(i=1;i<=n;i++){
while(sz>=lef && i-st[lef]>t)
lef++;
while(sz>=lef && v[i].c<(i-st[sz])*s+v[st[sz]].c)
sz--;
st[++sz]=i;
rasp=rasp+((i-st[lef])*s+v[st[lef]].c)*v[i].p;}
printf("%lld\n",rasp);
return 0;}