Cod sursa(job #1639298)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 8 martie 2016 11:43:24
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

ifstream fin ("branza.in");
ofstream fout ("branza.out");

#define MAXN 100050
#define MAXS 150
#define MAXC 10000050

int N, S, T;
long long C[MAXN], P[MAXN];
deque <long long> D;

int main()
{
    fin >>N >>S >>T;

    for (int i = 1; i <= N; ++i)
		fin >>C[i] >>P[i];

	long long solution = 0;

    for (int i = 1; i <= N; ++i)
	{
        int p = P[i];

        while (!D.empty() && C[i]*p <= C[D.back()]*p + S*p*(i - D.back()))
			D.pop_back();

		D.push_back(i);

		if (D.front() < i - T)
			D.pop_front();

		solution += C[D.front()]*p + S*p*(i- D.front());
	}

	fout <<solution <<'\n';

    return 0;
}