Cod sursa(job #3289192)

Utilizator stefan1010Stefan Bogdan stefan1010 Data 25 martie 2025 23:43:55
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int N,S,T,x;
int main()
{
	fin>>N>>S>>T;
	vector<int> v(N);
	deque<int> dq(N);
	long long total=0;
	for(int i=0; i<N; i++)
	{
		long long cost=0;
		fin>>v[i]>>x;
		while(!dq.empty())
		{
		    long long a,b;
            a=v[i]*x;
            b=v[dq.back()]*x+S*x*(i-dq.back());
            if(a<=b)
		        dq.pop_back();
		    else
		        break;
		}
		dq.push_back(i);
		if(dq.front()<i-T)
			dq.pop_front();
		cost=1LL*v[dq.front()]*x+S*(i-dq.front())*x;
		if(1LL*v[i]*x>cost)
			total+=cost;
		else
			total+=1LL*v[i]*x;
	}
	fout<<total;
	fin.close();
	fout.close();
	return 0;
}