#include <cstdio> #include <algorithm> using namespace std; struct block {int a; int w;}; block T[500000]; int A[500001]; long G[500001]; long H[500001]; int main() { int n, c; scanf("%i %i ", &n, &c); for (int i = 0; i<n; i++) scanf("%i %i ", &T[i].a, &T[i].w), A[T[i].w] = G[T[i].w] = H[T[i].w] = 0; A[0] = G[0] = H[0] = 0; sort(T, T+n, [&](block a, block b){return a.a<b.a;}); for (int i = 0; i<n; i++) { int a = T[i].a, w = T[i].w; if (a>A[w]) A[w] = a, G[w] = H[w]; if (a>A[0]) A[0] = a, G[0] = H[0]; H[w] = max(G[w], G[0]-c)+a; H[0] = max(H[0], H[w]); } printf("%li\n", H[0]); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include <cstdio> #include <algorithm> using namespace std; struct block {int a; int w;}; block T[500000]; int A[500001]; long G[500001]; long H[500001]; int main() { int n, c; scanf("%i %i ", &n, &c); for (int i = 0; i<n; i++) scanf("%i %i ", &T[i].a, &T[i].w), A[T[i].w] = G[T[i].w] = H[T[i].w] = 0; A[0] = G[0] = H[0] = 0; sort(T, T+n, [&](block a, block b){return a.a<b.a;}); for (int i = 0; i<n; i++) { int a = T[i].a, w = T[i].w; if (a>A[w]) A[w] = a, G[w] = H[w]; if (a>A[0]) A[0] = a, G[0] = H[0]; H[w] = max(G[w], G[0]-c)+a; H[0] = max(H[0], H[w]); } printf("%li\n", H[0]); return 0; } |