Submission #1238678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238678		k1r1t0	Catfish Farm (IOI22_fish)	C++20	100 / 100	238 ms	87060 KiB

fish

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 310000;
const ll INF = (ll)(1e18);

vector<array<int, 2>> pos[N];
vector<int> st[N];
vector<ll> dp[N][3];
ll cur[N], last[N];

// dp[i][0][a[i]] - max sum on pref if a[i - 1] >= a[i]
// dp[i][1][a[i]] - max sum on pref if a[i - 1] <= a[i]
// dp[i][2][x] - max sum on pref if a[i] = 0 & 1 ... x is already taken

void upd(ll &k, ll x) {
	k = max(k, x);
}

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
	for (int i = 0; i < m; i++)
		x[i]++, y[i]++;
	for (int i = 0; i < m; i++)
		pos[x[i]].push_back({y[i], w[i]});
	st[0].push_back(0);
	for (int i = 1; i <= n; i++) {
		sort(begin(pos[i]), end(pos[i]));
		st[i].push_back(0);
		st[i].push_back(n);
		for (auto [j, w] : pos[i - 1]) st[i].push_back(j);
		for (auto [j, w] : pos[i ^ 0]) st[i].push_back(j);
		for (auto [j, w] : pos[i + 1]) st[i].push_back(j);
		sort(begin(st[i]), end(st[i]));
		st[i].erase(unique(begin(st[i]), end(st[i])), end(st[i]));
	}
	for (int i = 0; i <= n; i++)
	for (int j = 0; j < 3; j++)
		dp[i][j] = vector<ll>(st[i].size(), -INF);
	dp[0][2][0] = 0;
	for (int i = 0; i <= n; i++) {
		for (auto [j, w] : pos[i]) cur[j] = w;
		
		int m = st[i].size();
		for (int j = m - 1; j > 0; j--)
			upd(dp[i][0][j - 1], dp[i][0][j] + cur[st[i][j]]);
		for (int j = 0; j < m - 1; j++)
			upd(dp[i][1][j + 1], dp[i][1][j] + last[st[i][j + 1]]);
		
		if (i > 0) {
			ll opt = -INF;
			int ptr = (int) st[i - 1].size() - 1;
			for (int j = m - 1; j >= 0; j--) {
				while (ptr >= 0 && st[i - 1][ptr] > st[i][j]) {
					upd(opt, dp[i - 1][2][ptr]);
					ptr--;
				}
				upd(dp[i][1][j], opt);
			}
		}
		
		upd(dp[i][0].back(), dp[i][1].back());
		
		if (i < n) {
			ll sum = 0;
			int ptr = 0;
			for (int j = 0; j < m; j++) {
				while (ptr < (int) pos[i + 1].size() && pos[i + 1][ptr][0] <= st[i][j]) {
					sum += pos[i + 1][ptr][1];
					ptr++;
				}
				int pos0 = upper_bound(begin(st[i + 1]), end(st[i + 1]), st[i][j]) - begin(st[i + 1]) - 1;
				upd(dp[i + 1][0][pos0], dp[i][0][j]);
				upd(dp[i + 1][2][pos0], dp[i][0][j] + sum);
				int pos1 = upper_bound(begin(st[i + 1]), end(st[i + 1]), st[i][j]) - begin(st[i + 1]) - 1;
				upd(dp[i + 1][1][pos1], dp[i][1][j]);
				upd(dp[i + 1][1][pos1], dp[i][2][j]);
			}
		}
		
		if (i > 0) for (auto [j, w] : pos[i - 1]) last[j] = 0;
		for (auto [j, w] : pos[i]) last[j] = w, cur[j] = 0;
	}
	ll ans = 0;
	for (int j = 0; j < 2; j++)
	for (ll k : dp[n][j])
		upd(ans, k);
	return ans;
}

/*

5 6
0 0 2000
0 2 20000000
0 3 10000000
1 1 100000000
1 3 1000000
1 4 10000000

5 4
0 2 5
1 1 2
4 4 1
3 3 3


*/


























/*
int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> X(M), Y(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
  }

  long long result = max_weights(N, M, X, Y, W);
  printf("%lld\n", result);
  return 0;
}
//*/

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