Cod sursa(job #1357585)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 23 februarie 2015 23:33:38
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <algorithm>
#define DIM 2001
#define f first
#define s second
using namespace std;

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

int N, M, i, j, k, ok, minim;
int D[DIM], t, val, pret, maxim;
int C, p, G, P[DIM], T[DIM];
pair <int , int> V[DIM];

int max(int a, int b){
     if(a >= b) return a;
     if(a <= b) return b;
}

void SetUp(){
     fin >> N >> C;
     for(i = 1; i <= N; i ++)
          fin >> V[i].f >> V[i].s;
     sort(V + 1, V + N + 1);
     for(i = 1; i <= N; i ++){
          T[i] = V[i].f;
          P[i] = V[i].s;
     }
     return;
}

void Dinamyc(){
     for(t = 1; t <= N; t ++){
          for(i = 1; i <= N; i ++){
               G = P[t]; if(P[i] < G) G = 0;
               D[i] = max(D[i-1] - (T[i] - T[i-1])*C + G, G - C);
               if(maxim < D[i]) maxim = D[i];
          }
     }
     fout << maxim;
     return;
}

int main(){
     SetUp();
     Dinamyc();
     return 0;
}