Cod sursa(job #447081)

Utilizator freak93Adrian Budau freak93 Data 27 aprilie 2010 17:21:54
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<fstream>

using namespace std;

const char iname[]="branza.in";
const char oname[]="branza.out";
const int maxn=100005;

ifstream f(iname);
ofstream g(oname);

long long n,i,a[maxn],j,deque[maxn],p,q,t,s,c[maxn],rez;

int main()
{
    f>>n>>s>>t;
    for(i=1;i<=n;++i)
        f>>a[i]>>c[i],a[i]-=(s*i);
    p=1;
    q=0;
    for(i=1;i<=n;++i)
    {
        while(p<=q&&a[deque[q]]>=a[i])
            --q;
        deque[++q]=i;
        rez+=(a[deque[p]]+s*i)*c[i];
        while(deque[p]<=i-t&&p<=q)
            ++p;
    }

    g<<rez<<"\n";

    f.close();
    g.close();

    return 0;
}