Cod sursa(job #1167160)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 4 aprilie 2014 14:57:36
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
// ce mare branza
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
long long  sol,n,s,t;
struct branza { long long pret, cantitate;} a[100014];
deque <long long > d;
int main()
{
    long long i,j,indcrt;
    fstream f,g;
    f.open("branza.in",ios::in);
    g.open("branza.out",ios::out);
    f>>n>>s>>t;
    for (i=1;i<=n;i++)
        f>>a[i].pret>>a[i].cantitate;
    for (i=1;i<=n;i++)
    {
        while (!d.empty() && a[d.back()].pret+(i-d.back())*s>=a[i].pret)
            d.pop_back();
        d.push_back(i);

            if (i-d.front()>t)
                d.pop_front();
        indcrt=d.front();
        sol=sol+(a[indcrt].pret+(i-indcrt)*s)*a[i].cantitate;
    }
    g<<sol;
}