Cod sursa(job #2732301)

Utilizator LacatusLacatus Catalin-Petru Lacatus Data 28 martie 2021 21:19:53
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <iostream>
#include<fstream>
using namespace std;
long deq[100000];
int main()
{ifstream f("branza.in");
 ofstream g("branza.out");
     long n,t,suma=0;
     int s;
     f>>n;
     f>>s;
     f>>t;
     long *a=new long[n];
     long *b=new long[n];
     for(int i=0;i<n;i++)
        f>>a[i]>>b[i];
     int start = 0, stop = -1;
	for (int i = 0; i < n; i++) {
		while (start <= stop && a[i] <= a[deq[stop]]+s*(i-deq[stop]))
			stop--;
		deq[++stop] = i;
		if (deq[start] == i-t-1)
			start++;

			suma += (a[deq[start]]+s*(i-deq[start]))*b[i];
	}
g<<suma;

     delete []b;
     delete []a;
    return 0;
}