Submission #1074090

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

fish

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#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	83 ms	23008 KB	Output is correct
2	Correct	83 ms	25980 KB	Output is correct
3	Correct	31 ms	12884 KB	Output is correct
4	Correct	30 ms	12892 KB	Output is correct
5	Correct	188 ms	42764 KB	Output is correct
6	Correct	201 ms	46932 KB	Output is correct

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Runtime error	853 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	30 ms	12856 KB	Output is correct
2	Correct	31 ms	12948 KB	Output is correct
3	Correct	52 ms	16220 KB	Output is correct
4	Correct	44 ms	16064 KB	Output is correct
5	Correct	74 ms	21076 KB	Output is correct
6	Correct	67 ms	20816 KB	Output is correct
7	Correct	83 ms	21072 KB	Output is correct
8	Correct	76 ms	21076 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	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	352 KB	Output is correct
7	Correct	0 ms	348 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	604 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	588 KB	Output is correct
13	Correct	0 ms	432 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	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	352 KB	Output is correct
7	Correct	0 ms	348 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	604 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	588 KB	Output is correct
13	Correct	0 ms	432 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	17 ms	604 KB	Output is correct
17	Execution timed out	1059 ms	5628 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	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	352 KB	Output is correct
7	Correct	0 ms	348 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	604 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	588 KB	Output is correct
13	Correct	0 ms	432 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	17 ms	604 KB	Output is correct
17	Execution timed out	1059 ms	5628 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	12856 KB	Output is correct
2	Correct	31 ms	12948 KB	Output is correct
3	Correct	52 ms	16220 KB	Output is correct
4	Correct	44 ms	16064 KB	Output is correct
5	Correct	74 ms	21076 KB	Output is correct
6	Correct	67 ms	20816 KB	Output is correct
7	Correct	83 ms	21072 KB	Output is correct
8	Correct	76 ms	21076 KB	Output is correct
9	Correct	77 ms	22864 KB	Output is correct
10	Correct	62 ms	13244 KB	Output is correct
11	Correct	119 ms	26364 KB	Output is correct
12	Correct	0 ms	348 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	31 ms	12972 KB	Output is correct
19	Correct	31 ms	12976 KB	Output is correct
20	Correct	31 ms	12892 KB	Output is correct
21	Correct	37 ms	12868 KB	Output is correct
22	Correct	90 ms	23380 KB	Output is correct
23	Correct	146 ms	33620 KB	Output is correct
24	Correct	132 ms	34644 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	23008 KB	Output is correct
2	Correct	83 ms	25980 KB	Output is correct
3	Correct	31 ms	12884 KB	Output is correct
4	Correct	30 ms	12892 KB	Output is correct
5	Correct	188 ms	42764 KB	Output is correct
6	Correct	201 ms	46932 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Runtime error	853 ms	2097152 KB	Execution killed with signal 9
9	Halted	0 ms	0 KB	-

Submission #1074090

Compilation message