Submission #1212994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212994		bangan	Catfish Farm (IOI22_fish)	C++20	52 / 100	1101 ms	291972 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define chmax(a, b) a = max(a, b)

const int maxn = 3030;

ll a[maxn][maxn];
ll b[maxn][maxn]; ll t[maxn][maxn];
ll c[maxn];
ll pre[maxn][maxn];

ll get(int x, int l, int r) {
	if (l>r) return 0;
	return pre[x][r] - pre[x][l-1];
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
	for (int i = 0; i < M; i++) pre[X[i]][Y[i] + 1] = W[i];
	for (int x = 0; x < N; x++) for (int y = 1; y <= N; y++) pre[x][y] += pre[x][y-1];
	c[1] = get(1, 1, N);
	FOR(i, 1, N) a[1][i] = get(0, 1, i);
	FOR(i, 1, N) b[1][i] = max(get(0, 1, i), get(1, i+1, N));
	FOR(i, 2, N-1) {
		FOR(j, 1, N) {
			chmax(a[i][j], a[i-1][j]);
			chmax(a[i][j], a[i][j-1] + get(i-1, j, j));
			chmax(a[i][j], c[i-2] + get(i-1, 1, j));
		}
		FOR(j, 1, N) {
			// FOR(k, 1, j) chmax(b[i][j], get(i-1, 1, j) + max(a[i-2][k], b[i-2][k]));
			chmax(b[i][j], b[i][j-1] + get(i-1, j, j));
			chmax(b[i][j], max(a[i-2][j], b[i-2][j]) + get(i-1, 1, j));
			chmax(b[i][j], c[i-2] + get(i-1, 1, j));
			chmax(b[i][j], a[i-1][j]);
			chmax(b[i][j], b[i][j-1] + get(i-1, j, j));
		}
		t[i][N] = b[i-1][N];
		for (int j=N-1; j>=1; j--) {
			chmax(t[i][j], b[i-1][j]);
			chmax(t[i][j], t[i][j+1] + get(i, j+1, j+1));
		}
		FOR(j, 1, N) chmax(b[i][j], t[i][j]);
		c[i] = c[i-1];
		FOR(j, 1, N) chmax(c[i], get(i, 1, j) + max(a[i-1][j], b[i-1][j]));
	}
	ll ans = c[N-1];
	FOR(i, 1, N) chmax(ans, a[N-1][i]);
	FOR(i, 1, N) chmax(ans, b[N-1][i]);
	// cout << b[3][4] << endl;
	return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16