Cod sursa(job #2546503)

Utilizator teisanumihai84Mihai Teisanu teisanumihai84 Data 14 februarie 2020 11:13:52
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.55 kb
#include <fstream>
#define dim 100001
using namespace std;
long long  C[dim], P[dim],  n, s, t, sol, i, v[dim], p, u;
int main()
{
    ifstream fin ("branza.in");
    ofstream fout ("branza.out");
    fin>>n>>s>>t;
    /// punem in deque
    for (i=1; i<=n; i++) {
        fin>>C[i]>>P[i];
        C[i]+=s*(n-i);
    }
    p=1; u=0;
    for (i=1; i<=n; i++)
    {
        while (C[i]<=C[v[u]] && p<=u)
            u--;
        v[++u]=i;
        if (v[u]-v[p]==t)
            p++;
        sol+=P[i]*(C[v[p]]-s*(n-i));
    }
    fout<<sol;
}