Submission #102081

#	Time	Username	Problem	Language	Result	Execution time	Memory
102081		ainta	Two Dishes (JOI19_dishes)	C++17	100 / 100	7990 ms	288000 KiB

dishes

#include<cstdio>
#include<algorithm>
#include<map>
#define N_ 1010000
#define SZ (1<<20)
#define pii pair<int,int>
using namespace std;
struct Input {
	int a;
	long long t, c;
}A[N_], B[N_];
long long SA[N_], SB[N_], res;
int n, m, cnt, DEBUG = 0;
struct Tree {
	long long Mx[SZ + SZ], K[SZ + SZ], INF = 1e18;
	void Add2(int nd, long long x) {
		Mx[nd] += x;
		K[nd] += x;
	}
	void Spread(int nd) {
		Add2(nd * 2, K[nd]);
		Add2(nd * 2 + 1, K[nd]);
		K[nd] = 0;
	}
	void UDT(int nd) {
		Mx[nd] = max(Mx[nd * 2], Mx[nd * 2 + 1]);
	}
	void Add(int nd, int b, int e, int s, int l, long long x) {
		if (s > l)return;
		if (b == s && e == l) {
			Add2(nd, x);
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (s <= m)Add(nd * 2, b, m, s, min(m, l), x);
		if (l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, x);
		UDT(nd);
	}
	long long Max(int nd, int b, int e, int s, int l) {
		if (s > l)return -INF;
		if (b == s && e == l) return Mx[nd];
		Spread(nd);
		int m = (b + e) >> 1;
		long long r = -INF;
		if (s <= m)r = max(r, Max(nd * 2, b, m, s, min(m, l)));
		if (l > m)r = max(r, Max(nd * 2 + 1, m + 1, e, max(m + 1, s), l));
		return r;
	}
	void Put(int nd, int b, int e, int x, long long y) {
		if (b == e) {
			if (Mx[nd] < y) {
				Mx[nd] = y, K[nd] = y;
			}
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (x <= m)Put(nd * 2, b, m, x, y);
		else Put(nd * 2 + 1, m + 1, e, x, y);
		UDT(nd);
	}
}TT;
int D[110][110];
int main() {
	srand(1879);
	int i, j;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++) {
		if (!DEBUG) {
			scanf("%d%lld%lld", &A[i].a, &A[i].t, &A[i].c);
		}
		else {
			A[i].a = rand() % 100;
			A[i].t = rand() % 300;
			A[i].c = rand() % 100 - 50;
		}
		SA[i] = SA[i - 1] + A[i].a;
	}
	for (i = 1; i <= m; i++) {
		if (!DEBUG) {
			scanf("%d%lld%lld", &B[i].a, &B[i].t, &B[i].c);
		}
		else {
			B[i].a = rand() % 100;
			B[i].t = rand() % 300;
			B[i].c = rand() % 100 - 50;
		}
		SB[i] = SB[i - 1] + B[i].a;
	}
	long long ss = 0;
	map<pii, int>Map;
	for (i = 1; i <= n; i++) {
		if (SA[i] > A[i].t) continue;
		if (SA[i] + SB[m] <= A[i].t) {
			ss += A[i].c;
			continue;
		}
		int pv = lower_bound(SB + 1, SB + m + 1, A[i].t - SA[i] + 1) - SB;
		pv--;
		Map[{i - 1, -(pv + 1)}] += A[i].c;
	}
	for (i = 1; i <= m; i++) {
		if (SB[i] > B[i].t) continue;
		if (SB[i] + SA[n] <= B[i].t) {
			ss += B[i].c;
			continue;
		}
		int pv = lower_bound(SA + 1, SA + n + 1, B[i].t - SB[i] + 1) - SA;
		pv--;
		ss += B[i].c;
		Map[{pv, -i}] -= B[i].c;
	}
	for (auto &tp : Map) {
		int x = tp.first.first, y = -tp.first.second, c  = tp.second;
		long long t = TT.Max(1, 0, SZ - 1, 0, y - 1);
		TT.Put(1, 0, SZ - 1, y, t);
		TT.Add(1, 0, SZ - 1, 0, y - 1, c);
	}
	printf("%lld\n", TT.Max(1, 0, SZ - 1, 0, SZ - 1) + ss);
	if (DEBUG) {
		for (i = 0; i <= n; i++)for (j = 0; j <= m; j++)D[i][j] = -1e9;
		D[0][0] = 0;
		for (i = 0; i <= n; i++) {
			for (j = 0; j <= m; j++) {
				if (i != n) {
					int t = D[i][j];
					if (SA[i + 1] + SB[j] <= A[i + 1].t)t += A[i + 1].c;
					D[i + 1][j] = max(D[i + 1][j], t);
				}
				if (j != m) {
					int t = D[i][j];
					if (SB[j + 1] + SA[i] <= B[j + 1].t)t += B[j + 1].c;
					D[i][j + 1] = max(D[i][j + 1], t);
				}
			}
		}
		printf("%d\n", D[n][m]);
	}
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:115:7: warning: unused variable 'x' [-Wunused-variable]
   int x = tp.first.first, y = -tp.first.second, c  = tp.second;
       ^
dishes.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:71:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%lld%lld", &A[i].a, &A[i].t, &A[i].c);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%lld%lld", &B[i].a, &B[i].t, &B[i].c);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9