Cod sursa(job #1113765)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 20 februarie 2014 21:29:44
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream>
#include <iomanip>

using namespace std;

typedef long long i64;

long long deq[100005], c[100005], pr;
long long n, i, s, t, p, u;

i64 sol;

int main() {
    ifstream f("branza.in");
    ofstream g("branza.out");
    f>>n>>s>>t;
    p=1;u=0;
    for(i=1;i<=n;i++) {
        f>>c[i]>>pr;
        while(u>0 && c[i]<=c[deq[u]]+s*(i-deq[u]))
            u--;
        u++;
        deq[u]=i;
        if(deq[p]<i-t)
            p++;
        sol=(i64)( sol + (i64)( c[deq[p]]+s*(i-deq[p]) )*pr );
    }

    g<<sol<<"\n";
    return 0;
}