Cod sursa(job #1938778)

Utilizator mariusn01Marius Nicoli mariusn01 Data 25 martie 2017 10:56:18
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#define DIM 100010
using namespace std;

long long d[DIM], c[DIM], p[DIM];

long long n, s, t, i, st, dr, sol;

ifstream fin ("branza.in");
ofstream fout("branza.out");

int main () {
    ifstream fin ("branza.in");
    ofstream fout("branza.out");

    fin>>n>>s>>t;
    for (i=1;i<=n;i++)
        fin>>c[i]>>p[i];

    d[1] = 1; st = 1; dr = 1;
    sol += c[1] * p[1];
    for (i=2; i<=n; i++) {
        while (st <= dr && c[i] <= (i-d[dr])*s + c[ d[dr] ])
            dr --;
        d[++dr] = i;
        if (i-d[st] == t+1)
            st++;
        sol += (c[ d[st] ] + s*(i-d[st])) * p[i];
    }
    fout<<sol;
    return 0;
}