Cod sursa(job #2048350)

Utilizator shantih1Alex S Hill shantih1 Data 25 octombrie 2017 22:43:13
Problema Carnati Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>

using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");

int cate, i, j, cpeh, mx, pr, co, ti, mx2, rez;

struct	om
{	int t, p;	} v[2005];
deque <int> vq, nq;

int max ()
{
	int mx = 0;
	for (j = 0; j < vq.size(); j++)
	{
		if (vq[j] <= pr)	nq[j]++;
		else nq[vq.size()-1]++;
		if (vq[j]*nq[j] > mx)	mx = vq[j]*nq[j];
	}
	return mx;
}

bool comp (om x, om y)
{
	return (x.t < y.t);
}

int main () {
	
	fin >> cate >> cpeh;
	for (i = 1; i <= cate; i++)
		fin >> v[i].t >> v[i].p;
	
	sort (v+1, v+cate+1, comp);
	
	rez = v[1].p-cpeh;
	vq.push_back(v[1].p);
	nq.push_back(1);
	ti = 1;
	for (i = 2; i <= cate; i++)
	{
		pr = v[i].p;	
		ti += v[i].t-v[i-1].t;
		co = ti*cpeh;
		vq.push_back(pr);
		nq.push_back(0);
		
		mx = max();
		mx -= co;
		mx2 = pr-cpeh;
		
		if (mx2 > mx)
		{
			mx = mx2;
			ti = 1;
			while (vq.size() > 1)
			{
				vq.pop_front();
				nq.pop_front();
			}
			nq[0] = 1;	
		}
		
		if (mx > rez)	rez = mx;
	}
	
	if (rez > 0)	fout << rez << "\n";
	else fout << 0 << "\n";
}