Cod sursa(job #2530554)

Utilizator vladth11Vlad Haivas vladth11 Data 24 ianuarie 2020 22:06:33
Problema Carnati Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"

using namespace std;
typedef long long ll;
int n,c,timp,minim = 2e9;
vector <int> t[1501];
vector <int> teste;
int v[1501];
int pretul(int x){
    int best = 0,sum = 0;
    for(int i = minim;i <= timp;i++){
        v[i] = -c;
        for(int j = t[i].size() - 1;j >= 0;j--){
            if(t[i][j] >= x){
                v[i] += x;
            }else{
                break;
            }
        }
        sum += v[i];
        if(sum > best){
            best = sum;
        }
        if(sum < 0)
            sum = 0;
    }
    return best;
}
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
int main()
{
    InParser cin("carnati.in");
    ofstream cout("carnati.out");

    cin >> n >> c;
    for(int i = 1;i <= n;i++){
        int x,y;
        cin >> x >> y;
        minim = min(minim,x);
        timp = max(timp,x);
        t[x].push_back(y);
        teste.push_back(y);
    }
    for(int i = minim;i <= timp;i++)
        sort(t[i].begin(),t[i].end(),less <int> ());
    int maxim = 0;
    for(int i = 0;i < n;i++){
        maxim = max(maxim,pretul(teste[i]));
    }
    cout << maxim;
    return 0;
}