Cod sursa(job #2207889)

Utilizator anamariatoaderAna Toader anamariatoader Data 27 mai 2018 10:55:08
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <fstream>

using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,s,m,i,q[100001],p,u;
struct numar{
    int p,c;
}v[100001];
long long sum;
int main()
{
    fin>>n>>s>>m;
    for(i=1;i<=n;i++)
        fin>>v[i].p>>v[i].c;
    p=0;
    u=-1;
    for(i=1;i<=n;i++){
        while(p<=u&&v[i].p<=v[q[u]].p+(i-q[u])*s)
            u--;
        q[++u]=i;
        while(p<=u&&i-q[p]>m)
            p++;
        sum+=1ll*v[q[p]].p*v[i].c+1ll*v[i].c*(i-q[p])*s;
    }
    fout<<sum;
    return 0;
}