Submission #1074089

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1074089	2024-08-25T07:50:19 Z	Gromp15	Catfish Farm (IOI22_fish)	C++17	40 / 100	1000 ms	2097152 KB

fish

#include <bits/stdc++.h>
#include "fish.h"
#define ll long long
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;

const ll INF = 1e18;
template<typename T> bool ckmin(T &a, const T &b ) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b ) { return a < b ? a = b, 1 : 0; }

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y, std::vector<int> w) {
	vector<vector<ar<ll, 2>>> each(n);
	for (int i = 0; i < m; i++) {
		each[x[i]].push_back({y[i], w[i]});
		each[x[i]].push_back({y[i]-1, 0});
	}
	for (int i = 0; i < n; i++) each[i].push_back({n-1, 0}), each[i].push_back({-1, 0});
	for (int i = 0; i < n; i++) {
		sort(all(each[i]));
		vector<ar<ll, 2>> nw;
		ll s = 0;
		for (int j = 0; j < sz(each[i]); j++) {
			int r = j;
			while (r+1 < sz(each[i]) && each[i][r+1][0] == each[i][r][0]) r++;
			for (int k = j; k <= r; k++) s += each[i][k][1];
			nw.push_back({each[i][j][0], s});
			j = r;
		}
		swap(each[i], nw);
	}
	vector<vector<ll>> dp;
	auto query = [&](int pos, int x) {
		return prev(upper_bound(all(each[pos]), ar<ll, 2>{x, LLONG_MAX})) - each[pos].begin();
	};
	vector<vector<ar<int, 3>>> val(n);
	for (int i = 0; i < n; i++) {
		val[i].resize(sz(each[i]));
		for (int k = 0; k < sz(each[i]); k++) {
			for (int j = -1; j <= 1; j++) {
				if (i + j >= 0 && i + j < n) {
					val[i][k][j+1] = query(i + j, each[i][k][0]);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		vector<vector<ll>> dp2;
		const int N = sz(each[i]);
		dp2.resize(i ? sz(each[i-1]) : 1, vector<ll>(N, -INF));
		if (!i) {
			for (int j = 0; j < N; j++) {
				dp2[0][j] = 0;
			}
			swap(dp, dp2);
		}
		else {
			for (int j = 0; j < sz(dp); j++) {
				for (int k = 0; k < sz(dp[j]); k++) {
					for (int l = 0; l < N; l++) {
						int L = k, R = max(i-2 >= 0 ? val[i-2][j][2] : 0, val[i][l][0]);
						ckmax(dp2[k][l], dp[j][k] + (L <= R ? each[i-1][R][1] - each[i-1][L][1] : 0));
					}
				}
			}
			swap(dp, dp2);
		}
	}
	ll ans = -INF;
	for (int i = 0; i < sz(dp); i++) {
		for (int j = 0; j < sz(dp[i]); j++) {
			int L = j, R = val[n-2][i][2];
			ckmax(ans, dp[i][j] + (L <= R ? each[n-1][R][1] - each[n-1][L][1] : 0));
		}
	}
	return ans;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	23004 KB	Output is correct
2	Correct	80 ms	25992 KB	Output is correct
3	Correct	31 ms	12888 KB	Output is correct
4	Correct	32 ms	12888 KB	Output is correct
5	Correct	198 ms	42780 KB	Output is correct
6	Correct	241 ms	47060 KB	Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	12864 KB	Output is correct
2	Correct	32 ms	12892 KB	Output is correct
3	Correct	53 ms	16464 KB	Output is correct
4	Correct	47 ms	16176 KB	Output is correct
5	Correct	76 ms	21688 KB	Output is correct
6	Correct	70 ms	21072 KB	Output is correct
7	Correct	82 ms	21724 KB	Output is correct
8	Correct	81 ms	21596 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	440 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	360 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	600 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	444 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	440 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	360 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	600 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	444 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	26 ms	756 KB	Output is correct
17	Execution timed out	1033 ms	5880 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	440 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	360 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	600 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	444 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	26 ms	756 KB	Output is correct
17	Execution timed out	1033 ms	5880 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	12864 KB	Output is correct
2	Correct	32 ms	12892 KB	Output is correct
3	Correct	53 ms	16464 KB	Output is correct
4	Correct	47 ms	16176 KB	Output is correct
5	Correct	76 ms	21688 KB	Output is correct
6	Correct	70 ms	21072 KB	Output is correct
7	Correct	82 ms	21724 KB	Output is correct
8	Correct	81 ms	21596 KB	Output is correct
9	Correct	86 ms	23124 KB	Output is correct
10	Correct	71 ms	14088 KB	Output is correct
11	Correct	125 ms	27720 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	436 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	30 ms	12892 KB	Output is correct
19	Correct	29 ms	12888 KB	Output is correct
20	Correct	32 ms	12760 KB	Output is correct
21	Correct	29 ms	12888 KB	Output is correct
22	Correct	95 ms	24400 KB	Output is correct
23	Correct	179 ms	35156 KB	Output is correct
24	Correct	148 ms	36180 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	23004 KB	Output is correct
2	Correct	80 ms	25992 KB	Output is correct
3	Correct	31 ms	12888 KB	Output is correct
4	Correct	32 ms	12888 KB	Output is correct
5	Correct	198 ms	42780 KB	Output is correct
6	Correct	241 ms	47060 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Execution timed out	1076 ms	2097152 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Submission #1074089

Compilation message