Cod sursa(job #998074)

Utilizator andrettiAndretti Naiden andretti Data 15 septembrie 2013 17:41:35
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
#include<algorithm>
#include<deque>
#define maxn 100005
using namespace std;

int n,s,t;
int c[maxn],p[maxn];
deque <int> q;
long long sol;

void read()
{
    scanf("%d%d%d",&n,&s,&t); t++;
    for(int i=1;i<=n;i++) scanf("%d%d",&c[i],&p[i]);
}

void solve()
{
    for(int i=1;i<=n;i++)
    {
        while(!q.empty() && 1LL*c[q.back()]+1LL*s*(i-q.back())>=c[i]) q.pop_back();
        q.push_back(i);

        if(q.front()==i-t) q.pop_front();
        sol+=1LL*(1LL*c[q.front()]+1LL*s*(i-q.front()))*p[i];
    }
}

int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);

    read();
    solve();
    printf("%lld",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}