Cod sursa(job #1417626)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 10 aprilie 2015 17:58:18
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
using namespace std;
int n, i, p, u, t, s;
long long c[100002], P[100002], d[100002], m[100002];
long long sum;
ifstream fin("branza.in");
ofstream fout("branza.out");
long long val(int i){
    return c[i] + (n - i) * 1LL * s;
}
int main(){
    fin>> n >> s >> t;
    for(i = 1; i <= n; i++){
        fin>> c[i] >> P[i];
    }
    m[1] = c[1];
    p = u = d[1] = 1;
    for(i = 2; i <= n; i++){
        m[i] = min(c[i], val(d[p]) - (n - i) * 1LL * s);
        while(p <= u && val(d[u]) > val(i)){
            u--;
        }
        u++;
        d[u] = i;
        if(i - d[p] == t){
            p++;
        }
    }
    for(i = 1; i <= n; i++){
        sum += m[i] * P[i];
    }
    fout<< sum <<"\n";
    return 0;
}