Cod sursa(job #1895454)

Utilizator raluca1234Tudor Raluca raluca1234 Data 27 februarie 2017 23:13:35
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#include <algorithm>

#define maxN 2000

using namespace std;

int N, C;
struct client{
  int T, P;
}v[maxN + 1];

inline bool cmp(client A, client B){
  if (A.T == B.T)
    return A.P < B.P;
  return A.T < B.T;
}

inline int maximum(int a, int b){ return (a > b ? a : b);}

int totalPrice(int P){
  int maxs, s;
  maxs=s=0;
  for (int i = 1 ; i <= N; i++){
    s=maximum(s-(v[i].T-v[i-1].T)*C, 0);
    if (P<=v[i].P)
      s+=P;
    maxs=maximum(maxs, s-C);
  }
  return maxs;
}

int main(){
  freopen("carnati.in", "r", stdin);
  freopen("carnati.out", "w", stdout);

  scanf("%d%d", &N, &C);
  for (int i = 1; i <= N; i++)
    scanf("%d%d", &v[i].T, &v[i].P);

  sort(v + 1, v + N + 1, cmp);

  int ans=0;
  for (int i = 1; i <= N; i++)
    ans=maximum(ans, totalPrice(v[i].P));

  printf("%d\n", ans);

  return 0;
}