Cod sursa(job #2638170)

Utilizator PredescuSebastianIonPredescu Sebastian Ion PredescuSebastianIon Data 27 iulie 2020 13:31:32
Problema Branza Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream>
#define dim 10001

using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
long long a[dim],b[dim],n,s,t,sol,v[dim],p,u;
int main()
{
    f>>n>>s>>t;
    for(int i=1;i<=n;i++)
    {
        f>>a[i]>>b[i];
        a[i]+=s*(n-i);
    }
    p=1;
    u=0;
    for(int i=1;i<=n;i++)
    {
        while(a[i]<=a[v[u]] && p<=u)
        {
            u--;
        }
        v[++u]=i;
        if(v[u]-v[p]==t+1)
        {
            p++;
        }
        sol+=b[i]*(a[v[p]]-s*(n-i));
    }
    g<<sol<<'\n';
    return 0;
}