Submission #833328

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
833328	2023-08-22T04:35:52 Z	pavement	Catfish Farm (IOI22_fish)	C++17	61 / 100	1000 ms	58272 KB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

#define eb emplace_back
#define mp make_pair

using ll = long long;
using ii = pair<int, int>;

int N, M;
vector<int> X, Y, W;
vector<vector<ll> > mem;
vector<ii> col[100005];

ll dp(int p, int ty) {
	ll ret = 0;
	if (ty == 0) {
		if (p == 0) {
			return 0;
		}
		if (p < 0) {
			return -(ll)1e16;
		}
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		ret = max({ret, dp(p - 1, 0), dp(p - 1, 1)});
		if (p && !col[p - 1].empty()) {
			ret = max(ret, dp(col[p - 1][0].second, 2));
		}
	} else if (ty == 1) {
		if (p == 0) {
			return 0;
		}
		if (p < 0) {
			return -(ll)1e16;
		}
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		ret = max({ret, dp(p - 1, 0), dp(p - 1, 1)});
		if (p && !col[p - 1].empty()) {
			ret = max(ret, dp(col[p - 1][0].second, 2));
			ret = max(ret, dp(col[p - 1].back().second, 3));
		}
	} else if (ty == 2) {
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		int x = X[p], y = Y[p];
		ll sum_all = 0;
		int ptr = lower_bound(col[x].begin(), col[x].end(), mp(y, p)) - col[x].begin();
		assert(ptr != (int)col[x].size());
		for (int i = ptr; i < (int)col[x].size(); i++) {
			sum_all += W[col[x][i].second];
		}
		ret = max(ret, dp(x - 1, 1) + sum_all);
		if (x && !col[x - 1].empty()) {
			ll sum_cur = 0;
			for (auto [y_p, idx_p] : col[x - 1]) {
				if (y_p <= y) {
					continue;
				}
				while (ptr < (int)col[x].size() && y_p > Y[col[x][ptr].second]) {
					sum_cur += W[col[x][ptr].second];
					ptr++;
				}
				ret = max(ret, dp(idx_p, 2) + sum_cur);
			}
		}
	} else {
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		int x = X[p], y = Y[p];
		ll sum_all = 0;
		int ptr = lower_bound(col[x].begin(), col[x].end(), mp(y, p)) - col[x].begin();
		assert(ptr != (int)col[x].size());
		for (int i = ptr; i >= 0; i--) {
			sum_all += W[col[x][i].second];
		}
		ret = max(ret, dp(x, 0) + sum_all);
		if (x && !col[x - 1].empty()) {
			ll sum_cur = 0;
			for (int _ = (int)col[x - 1].size() - 1; _ >= 0; _--) {
				auto [y_p, idx_p] = col[x - 1][_];
				if (y_p >= y) {
					continue;
				}
				while (ptr >= 0 && y_p < Y[col[x][ptr].second]) {
					sum_cur += W[col[x][ptr].second];
					ptr--;
				}
				//~ cout << "DP " << p << ' ' << ty << " TO " << idx_p << ' ' << 3 << ' ' << sum_cur << ' ' << y_p << ' ' << y << '\n';
				ret = max(ret, dp(idx_p, 3) + sum_cur);
			}
		}
	}
	//~ cout << "DP " << p << ' ' << ty << ' ' << ret << '\n';
	return mem[p][ty] = ret;
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	::N = N;
	::M = M;
	::X = X;
	::Y = Y;
	::W = W;
	mem = vector<vector<ll> >(N + M, vector<ll>(4, -1));
	for (int i = 0; i < M; i++) {
		col[X[i]].eb(Y[i], i);
	}
	for (int i = 0; i < N; i++) {
		sort(col[i].begin(), col[i].end());
	}
	return dp(N, 0);
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	29520 KB	Output is correct
2	Correct	48 ms	33584 KB	Output is correct
3	Correct	18 ms	22228 KB	Output is correct
4	Correct	14 ms	22116 KB	Output is correct
5	Correct	119 ms	56532 KB	Output is correct
6	Correct	146 ms	58272 KB	Output is correct

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Execution timed out	1089 ms	38696 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	22228 KB	Output is correct
2	Correct	15 ms	22228 KB	Output is correct
3	Correct	57 ms	27604 KB	Output is correct
4	Correct	31 ms	27732 KB	Output is correct
5	Correct	73 ms	37632 KB	Output is correct
6	Correct	63 ms	36888 KB	Output is correct
7	Correct	75 ms	37400 KB	Output is correct
8	Correct	79 ms	37484 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	2 ms	2656 KB	Output is correct
6	Correct	1 ms	2652 KB	Output is correct
7	Correct	1 ms	2644 KB	Output is correct
8	Correct	1 ms	2644 KB	Output is correct
9	Correct	2 ms	2664 KB	Output is correct
10	Correct	3 ms	2916 KB	Output is correct
11	Correct	2 ms	2772 KB	Output is correct
12	Correct	2 ms	2772 KB	Output is correct
13	Correct	1 ms	2644 KB	Output is correct
14	Correct	3 ms	2772 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	2 ms	2656 KB	Output is correct
6	Correct	1 ms	2652 KB	Output is correct
7	Correct	1 ms	2644 KB	Output is correct
8	Correct	1 ms	2644 KB	Output is correct
9	Correct	2 ms	2664 KB	Output is correct
10	Correct	3 ms	2916 KB	Output is correct
11	Correct	2 ms	2772 KB	Output is correct
12	Correct	2 ms	2772 KB	Output is correct
13	Correct	1 ms	2644 KB	Output is correct
14	Correct	3 ms	2772 KB	Output is correct
15	Correct	2 ms	2644 KB	Output is correct
16	Correct	3 ms	2900 KB	Output is correct
17	Correct	159 ms	8684 KB	Output is correct
18	Correct	146 ms	9004 KB	Output is correct
19	Correct	74 ms	8864 KB	Output is correct
20	Correct	74 ms	8848 KB	Output is correct
21	Correct	77 ms	8908 KB	Output is correct
22	Correct	308 ms	15052 KB	Output is correct
23	Correct	10 ms	3924 KB	Output is correct
24	Correct	44 ms	6740 KB	Output is correct
25	Correct	3 ms	2772 KB	Output is correct
26	Correct	11 ms	3796 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	2 ms	2656 KB	Output is correct
6	Correct	1 ms	2652 KB	Output is correct
7	Correct	1 ms	2644 KB	Output is correct
8	Correct	1 ms	2644 KB	Output is correct
9	Correct	2 ms	2664 KB	Output is correct
10	Correct	3 ms	2916 KB	Output is correct
11	Correct	2 ms	2772 KB	Output is correct
12	Correct	2 ms	2772 KB	Output is correct
13	Correct	1 ms	2644 KB	Output is correct
14	Correct	3 ms	2772 KB	Output is correct
15	Correct	2 ms	2644 KB	Output is correct
16	Correct	3 ms	2900 KB	Output is correct
17	Correct	159 ms	8684 KB	Output is correct
18	Correct	146 ms	9004 KB	Output is correct
19	Correct	74 ms	8864 KB	Output is correct
20	Correct	74 ms	8848 KB	Output is correct
21	Correct	77 ms	8908 KB	Output is correct
22	Correct	308 ms	15052 KB	Output is correct
23	Correct	10 ms	3924 KB	Output is correct
24	Correct	44 ms	6740 KB	Output is correct
25	Correct	3 ms	2772 KB	Output is correct
26	Correct	11 ms	3796 KB	Output is correct
27	Correct	3 ms	3668 KB	Output is correct
28	Execution timed out	1032 ms	32564 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	22228 KB	Output is correct
2	Correct	15 ms	22228 KB	Output is correct
3	Correct	57 ms	27604 KB	Output is correct
4	Correct	31 ms	27732 KB	Output is correct
5	Correct	73 ms	37632 KB	Output is correct
6	Correct	63 ms	36888 KB	Output is correct
7	Correct	75 ms	37400 KB	Output is correct
8	Correct	79 ms	37484 KB	Output is correct
9	Correct	79 ms	37272 KB	Output is correct
10	Correct	55 ms	26188 KB	Output is correct
11	Correct	142 ms	49968 KB	Output is correct
12	Correct	2 ms	2644 KB	Output is correct
13	Correct	2 ms	2768 KB	Output is correct
14	Correct	2 ms	2644 KB	Output is correct
15	Correct	2 ms	2644 KB	Output is correct
16	Correct	2 ms	2644 KB	Output is correct
17	Correct	1 ms	2644 KB	Output is correct
18	Correct	14 ms	22228 KB	Output is correct
19	Correct	17 ms	22200 KB	Output is correct
20	Correct	14 ms	22228 KB	Output is correct
21	Correct	13 ms	22200 KB	Output is correct
22	Correct	67 ms	36904 KB	Output is correct
23	Correct	136 ms	49972 KB	Output is correct
24	Correct	157 ms	50508 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	29520 KB	Output is correct
2	Correct	48 ms	33584 KB	Output is correct
3	Correct	18 ms	22228 KB	Output is correct
4	Correct	14 ms	22116 KB	Output is correct
5	Correct	119 ms	56532 KB	Output is correct
6	Correct	146 ms	58272 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Execution timed out	1089 ms	38696 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Submission #833328

Compilation message