Cod sursa(job #326227)

Utilizator savimSerban Andrei Stan savim Data 24 iunie 2009 12:56:44
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>

#define MAX_N 2048

int n, m, c, i, j, sol;
int V[2 * MAX_N];
int T[MAX_N], A[MAX_N];

void cit() {
	freopen("carnati.in", "r", stdin);
	freopen("carnati.out", "w", stdout);

	scanf("%d %d", &n, &c);
	for (i = 1; i <= n; i++)
		scanf("%d %d", &T[i], &A[i]);
}

void solve() {
	for (i = 1; i <= n; i++) {
		//fixez pretul carnatului i
		m = 0;
		for (j = 1; j <= n; j++) {
			if (A[j] >= A[i])
				V[++m] = A[i] - c;
			else 
				V[++m] = -c;
			if (j < n) 
				V[++m] = -(T[j + 1] - T[j] - 1) * c;
		}                
	
    	//subsecventa de suma maxima, vad cat obtin
    	int sum = 0;
		for (j = 1; j <= m; j++) {
			if (sum + V[j] >= 0)
				sum += V[j];
			else sum = 0;
			
			if (sum > sol) sol = sum;
		}
	}
	
	printf("%d\n", sol);	
}

int main() {

	cit();
	solve();

	return 0;
}