Cod sursa(job #2094248)

Utilizator DimaTCDima Trubca DimaTC Data 25 decembrie 2017 13:52:36
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<bits/stdc++.h>
#define t first
#define c second

using namespace std;

int n,C;
int p,tp,tn,pr;
long long rs;
pair<int,int> a[2010];
int dp[2010];

int main() {
	ifstream cin("carnati.in");
	ofstream cout("carnati.out");
	cin>>n>>C;
	
	for (int i=1; i<=n; i++) {
		cin>>a[i].t>>a[i].c;
	}
	
	rs=-(1LL<<55);
	for (int i=1; i<=n; i++) {
		
		p=a[i].c;
		
		if (a[1].c>=p) {
			dp[1] = p; tp=a[1].t;
		} else dp[1] = 0, tp=-1;
		
		for (int i=2; i<=n; i++) {
			if (a[i].c>=p) {
				if (tp==-1) tp=a[i].t;
				dp[i]=max(p, dp[i-1]-(a[i].t-tp)*C+p);
				tp=a[i].t;
			} else {
				dp[i] = max(0, dp[i-1]-(a[i].t-tp)*C);
				tp=a[i].t; 
			}

		}
		
		for (int i=1; i<=n; i++) {
			if (dp[i]>rs) rs=dp[i];
		}
		
	}
	
	cout<<rs-C;
	return 0;
}