Submission #1074102

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1074102	2024-08-25T07:59:35 Z	Gromp15	Catfish Farm (IOI22_fish)	C++17	12 / 100	931 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 k = 0; k < sz(dp[0]); k++) {
				for (int l = 0; l < N; l++) {
					// val[i-2][j][2] <= val[i][l][0]
					int ans = 0;
					{
						int l = 0, r = i-2 >= 0 ? sz(each[i-2]) - 1 : -1;
						while (l <= r) {
							int mid = (l+r)/2;
							if (val[i-2][mid][2] <= val[i][l][0]) ans = mid, l = mid+1;
							else r = mid-1;
						}
					}
					for (int j = 0; j <= ans; j++) {
						int L = k, R = val[i][l][0];
						ckmax(dp2[k][l], dp[j][k] + (L <= R ? each[i-1][R][1] - each[i-1][L][1] : 0));
					}
					for (int j = ans+1; j < sz(dp); j++) {
						int L = k, R = val[i-2][j][2];
						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	70 ms	23004 KB	Output is correct
2	Correct	108 ms	25836 KB	Output is correct
3	Correct	38 ms	12892 KB	Output is correct
4	Correct	32 ms	12884 KB	Output is correct
5	Correct	198 ms	42764 KB	Output is correct
6	Correct	217 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	Runtime error	931 ms	2097152 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	12888 KB	Output is correct
2	Correct	30 ms	12892 KB	Output is correct
3	Correct	58 ms	16468 KB	Output is correct
4	Correct	51 ms	16080 KB	Output is correct
5	Correct	105 ms	21804 KB	Output is correct
6	Correct	81 ms	21076 KB	Output is correct
7	Correct	73 ms	21584 KB	Output is correct
8	Correct	86 ms	21632 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	432 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Incorrect	1 ms	348 KB	1st lines differ - on the 1st token, expected: '56941582046', found: '56900089829'
14	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	432 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Incorrect	1 ms	348 KB	1st lines differ - on the 1st token, expected: '56941582046', found: '56900089829'
14	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	432 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Incorrect	1 ms	348 KB	1st lines differ - on the 1st token, expected: '56941582046', found: '56900089829'
14	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	12888 KB	Output is correct
2	Correct	30 ms	12892 KB	Output is correct
3	Correct	58 ms	16468 KB	Output is correct
4	Correct	51 ms	16080 KB	Output is correct
5	Correct	105 ms	21804 KB	Output is correct
6	Correct	81 ms	21076 KB	Output is correct
7	Correct	73 ms	21584 KB	Output is correct
8	Correct	86 ms	21632 KB	Output is correct
9	Correct	92 ms	23120 KB	Output is correct
10	Correct	65 ms	14084 KB	Output is correct
11	Correct	173 ms	27648 KB	Output is correct
12	Correct	0 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	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	29 ms	12892 KB	Output is correct
19	Correct	32 ms	12892 KB	Output is correct
20	Correct	32 ms	12892 KB	Output is correct
21	Correct	34 ms	12872 KB	Output is correct
22	Incorrect	102 ms	24144 KB	1st lines differ - on the 1st token, expected: '45561826463480', found: '45065264384913'
23	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	23004 KB	Output is correct
2	Correct	108 ms	25836 KB	Output is correct
3	Correct	38 ms	12892 KB	Output is correct
4	Correct	32 ms	12884 KB	Output is correct
5	Correct	198 ms	42764 KB	Output is correct
6	Correct	217 ms	47060 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Runtime error	931 ms	2097152 KB	Execution killed with signal 9
9	Halted	0 ms	0 KB	-

Submission #1074102

Compilation message