Cod sursa(job #2731302)

Utilizator SofeiAndreiSofei Andrei SofeiAndrei Data 27 martie 2021 17:33:49
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
int n,k,i,primul,ultimul;
short taxa;
long long S;
long long x[100001],Deque[100001],cerere[100001];
int main()
{
    f>>n>>taxa>>k;
    k++;
    for(i=1;i<=n;i++){
        f>>x[i]>>cerere[i];
    }
    S=0;
    primul=1;
    ultimul=0;
    for(i=1;i<=n;i++){
        while(x[i]<=x[Deque[ultimul]]+taxa*(i-Deque[ultimul])){
            if(primul>ultimul){
                break;
            }
            else{
                ultimul--;
            }
        }
        ultimul++;
        Deque[ultimul]=i;
        if(Deque[primul]==i-k){
            //am ajuns la o secventa de lungime k, asa ca nu mai avem nevoie de primul
            primul++;
        }
        S=S+(x[Deque[primul]]+taxa*(i-Deque[primul]))*cerere[i];
    }
    g<<S;
    return 0;
}