Cod sursa(job #850844)

Utilizator razvan.popaPopa Razvan razvan.popa Data 9 ianuarie 2013 00:10:58
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#define infile "carnati.in"
#define outfile "carnati.out"
#define INF (1<<30)
#define nxt (*it)
#define nMax 2005
#define FOR(g)\
   for(vector<int>::iterator it=g.begin(); it!=g.end(); ++it)
using namespace std;

struct client{
    int t, p;
} A[nMax];

int N, C;

int Sol = -INF;


void read(){
    ifstream f(infile);

    f >> N >> C;

    for(int i=1; i<=N; ++i)
       f >> A[i].t >> A[i].p;
    A[0].t = A[0].p = -10;

    f.close();
}

bool cmp(const client &a, const client &b){
    return a.t < b.t;
}

void solve(){
    sort(A+1, A+N+1, cmp);

    for(int i=1; i<=N; ++i){
        int x, p, s = 0;

        for(int j=1; j<=N; ++j){
            p = A[i].p * (A[i].p <= A[j].p);
            x = p - (A[j].t - A[j-1].t) * C;

            if(s + x < p - C)
               s = p - C;
            else
               s += x;

            Sol = max(Sol, s);
        }
    }
}

void print(){
    ofstream g(outfile);

    g << Sol << '\n';

    g.close();
}

int main(){
    read();
    solve();
    print();

    return 0;
}