Submission #375836

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375836	2021-03-10T04:09:24 Z	Kevin_Zhang_TW	Two Dishes (JOI19_dishes)	C++17	10 / 100	195 ms	32076 KB

dishes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif 
const int MAX_N = 2010, MAX_M = 1000010;

const ll inf = 1ll << 60;

ll n[2], a[2][MAX_M], tl[2][MAX_M], w[2][MAX_M];

int ch[2][MAX_M];

ll dur[2][MAX_M];

ll dp[MAX_N][MAX_N];

struct bit {
	int n;
	vector<ll> val;
	bit(int _n = 0) : n(_n + 10) {
		val.resize(n);
	}
	void add(int i, ll v) {
		for (;i < n;i += i&-i)
			val[i] += v;
	}
	ll qry(int i) {
		ll res = 0;
		for (;i;i ^= i&-i) 
			res += val[i];
		return res;
	}
};

ll lost[2][MAX_M];

void hoolan() {
	bit tree[2];

	ll res = 0;

	for (int k = 0;k < 2;++k) {
		for (int i = 1;i <= n[k];++i) {
			ll ct = dur[k][i], more = tl[k][i] - ct;
			if (more < 0) w[k][i] = 0;
			ch[k][i] = upper_bound(dur[k^1], dur[k^1] + n[k^1] + 1, max(0ll, more)) - dur[k^1];
			lost[k^1][ ch[k][i] ] += w[k][i];

			res += w[k][i];
		}
	}

	int p[2] {} ;

	while (p[0] < n[0] || p[1] < n[1]) {
		ll cost = inf, sd = -1;
		for (int k = 0;k < 2;++k) {
			if (p[k] == n[k]) continue;
			if (chmin(cost, lost[k][ p[k] ]))
				sd = k;
		}
		res -= cost;
		lost[sd^1][ ch[sd][ p[sd] ] ] -= w[sd][ p[sd] ];
		++p[sd];
	}

	cout << res << '\n';
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n[0] >> n[1];

	for (int k = 0;k < 2;++k)
		for (int i = 1;i <= n[k];++i)
			cin >> a[k][i] >> tl[k][i] >> w[k][i];

	for (int k = 0;k < 2;++k) {
		for (int i = 1;i <= n[k];++i)
			dur[k][i] = dur[k][i-1] + a[k][i];
	}

	if (max(n[0], n[1]) > 2000) {
		hoolan();
		return 0;
	}

	for (int i = 0;i <= n[0];++i)
		for (int j = 0;j <= n[1];++j)
			dp[i][j] = -inf;
	dp[0][0] = 0;

	for (int i = 0;i <= n[0];++i)
		for (int j = 0;j <= n[1];++j) {
			ll ct = dur[0][i] + dur[1][j];
			chmax(dp[i+1][j], dp[i][j] +
					(ct + a[0][i+1] <= tl[0][i+1] ? w[0][i+1] : 0));
			chmax(dp[i][j+1], dp[i][j] +
					(ct + a[1][j+1] <= tl[1][j+1] ? w[1][j+1] : 0));
		}

	cout << dp[n[0]][n[1]] << '\n';
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	192 ms	17388 KB	Output is correct
2	Incorrect	195 ms	17004 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	492 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	1 ms	492 KB	Output is correct
13	Correct	1 ms	492 KB	Output is correct
14	Correct	1 ms	492 KB	Output is correct
15	Correct	1 ms	492 KB	Output is correct
16	Correct	1 ms	492 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	492 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	1 ms	492 KB	Output is correct
13	Correct	1 ms	492 KB	Output is correct
14	Correct	1 ms	492 KB	Output is correct
15	Correct	1 ms	492 KB	Output is correct
16	Correct	1 ms	492 KB	Output is correct
17	Correct	40 ms	32076 KB	Output is correct
18	Correct	29 ms	31980 KB	Output is correct
19	Correct	41 ms	31980 KB	Output is correct
20	Correct	38 ms	32000 KB	Output is correct
21	Correct	34 ms	30828 KB	Output is correct
22	Correct	37 ms	31980 KB	Output is correct
23	Correct	38 ms	31980 KB	Output is correct

Subtask #4
0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	492 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	1 ms	492 KB	Output is correct
13	Correct	1 ms	492 KB	Output is correct
14	Correct	1 ms	492 KB	Output is correct
15	Correct	1 ms	492 KB	Output is correct
16	Correct	1 ms	492 KB	Output is correct
17	Correct	40 ms	32076 KB	Output is correct
18	Correct	29 ms	31980 KB	Output is correct
19	Correct	41 ms	31980 KB	Output is correct
20	Correct	38 ms	32000 KB	Output is correct
21	Correct	34 ms	30828 KB	Output is correct
22	Correct	37 ms	31980 KB	Output is correct
23	Correct	38 ms	31980 KB	Output is correct
24	Incorrect	163 ms	14572 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	492 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	1 ms	492 KB	Output is correct
13	Correct	1 ms	492 KB	Output is correct
14	Correct	1 ms	492 KB	Output is correct
15	Correct	1 ms	492 KB	Output is correct
16	Correct	1 ms	492 KB	Output is correct
17	Correct	40 ms	32076 KB	Output is correct
18	Correct	29 ms	31980 KB	Output is correct
19	Correct	41 ms	31980 KB	Output is correct
20	Correct	38 ms	32000 KB	Output is correct
21	Correct	34 ms	30828 KB	Output is correct
22	Correct	37 ms	31980 KB	Output is correct
23	Correct	38 ms	31980 KB	Output is correct
24	Incorrect	163 ms	14572 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	492 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	492 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	1 ms	492 KB	Output is correct
13	Correct	1 ms	492 KB	Output is correct
14	Correct	1 ms	492 KB	Output is correct
15	Correct	1 ms	492 KB	Output is correct
16	Correct	1 ms	492 KB	Output is correct
17	Correct	40 ms	32076 KB	Output is correct
18	Correct	29 ms	31980 KB	Output is correct
19	Correct	41 ms	31980 KB	Output is correct
20	Correct	38 ms	32000 KB	Output is correct
21	Correct	34 ms	30828 KB	Output is correct
22	Correct	37 ms	31980 KB	Output is correct
23	Correct	38 ms	31980 KB	Output is correct
24	Incorrect	163 ms	14572 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #7
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	192 ms	17388 KB	Output is correct
2	Incorrect	195 ms	17004 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	192 ms	17388 KB	Output is correct
2	Incorrect	195 ms	17004 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Submission #375836

Compilation message