oj.uz

Submission #749791

# Submission time Handle Problem Language Result Execution time Memory
749791 2023-05-28T13:43:45 Z happypotato Catfish Farm (IOI22_fish) C++17
23 / 100
 814 ms 118584 KB 
#include "fish.h"
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
 
long long max_weights(int32_t n, int32_t m, vector<int32_t> X, vector<int32_t> Y,
					vector<int32_t> W) {
	
	for (int i = 0; i < m; i++) {
		X[i]++; Y[i]++;
	}

	// int olda[n + 1][n + 1];
	// for (int i = 0; i <= n; i++) {
	// 	for (int j = 0; j <= n; j++) {
	// 		olda[i][j] = 0;
	// 	}
	// }
	// for (int i = 0; i < m; i++) {
	// 	olda[X[i]][Y[i]] = W[i];
	// }
	// int oldps[n + 1][n + 1]; // ps[i][j] = a[i][1] + ... + a[i][j]
	// for (int i = 1; i <= n; i++) {
	// 	oldps[i][0] = 0;
	// 	for (int j = 1; j <= n; j++) {
	// 		oldps[i][j] = oldps[i][j - 1] + olda[i][j];
	// 	}
	// }

	vector<pii> a[n + 1], ps[n + 1];
	set<pii> critpts;
	for (int i = 1; i <= n; i++) {
		a[i].pb({0, 0});
		ps[i].pb({0, 0});
		critpts.insert({i, 0});
		critpts.insert({i, n});
	}
	for (int i = 0; i < m; i++) {
		a[X[i]].pb({Y[i], W[i]});
		// critical points: (X[i] +- 1, Y[i]), (X[i], Y[i] - 1)
		if (X[i] > 1) {
			critpts.insert({X[i] - 1, Y[i]});
		}
		if (X[i] < n) {
			critpts.insert({X[i] + 1, Y[i]});
		}
		critpts.insert({X[i], Y[i] - 1});
	}
	for (int i = 1; i <= n; i++) {
		sort(a[i].begin(), a[i].end());
		for (pii &x : a[i]) {
			ps[i].pb({x.ff, ps[i].back().ss + x.ss});
		}
	}

	function<int(int, int)> GetPS = [&](int x, int y) -> int {
		int lb = 0, rb = (int)(ps[x].size()) - 1;
		while (lb < rb) {
			int mid = (lb + rb + 1) >> 1;
			if (ps[x][mid].ff <= y) lb = mid;
			else rb = mid - 1;
		}
		return ps[x][lb].ss;
	};
	
	// int olddp[2][n + 1][n + 1];
	// // olddp[increasing][pos][height] = max ans from 1 to pos with pos getting height, height must be increasing
	// for (int i = 0; i <= n; i++) {
	// 	olddp[0][0][i] = olddp[1][0][i] = (i == 0 ? 0 : -1e18);
	// 	olddp[0][1][i] = olddp[1][1][i] = 0;
	// }
	// int oldcur[n + 1];
	// function<void(void)> resetoldcur = [&]() {
	// 	for (int i = 0; i <= n; i++) oldcur[i] = 0;
	// };

	vector<vector<pii>> dp[2];
	dp[0].resize(n + 1); dp[1].resize(n + 1);
	for (int i = 0; i <= n; i++) {
		dp[0][0].pb({i, (i == 0 ? 0 : -1e18)});
		dp[1][0].pb({i, (i == 0 ? 0 : -1e18)});
		
		dp[0][1].pb({i, 0});
		dp[1][1].pb({i, 0});
	}
	for (pii x : critpts) {
		if (x.ff < 2) continue;
		dp[0][x.ff].pb({x.ss, 0});
		dp[1][x.ff].pb({x.ss, 0});
	}
	vector<pii> cur;
 
	for (int i = 2; i <= n; i++) {
		// for (int j = 0; j <= n; j++) {
		// 	olddp[0][i][j] = olddp[1][i][j] = 0;
		// }
		sort(dp[0][i].begin(), dp[0][i].end());
		sort(dp[1][i].begin(), dp[1][i].end());
		// Case 0: height of i is 0
		// resetoldcur();
		// olddp[0][i][0] = max(olddp[0][i - 1][0], olddp[1][i - 1][0]);
		// for (int j = 1; j <= n; j++) {
		// 	olddp[0][i][0] = max(olddp[0][i][0], max(olddp[0][i - 1][j], olddp[1][i - 1][j]) + oldps[i][j]);
		// }
		// olddp[1][i][0] = olddp[0][i][0];

		{
			// dp[flag][i][0].ff is always 0
			for (int j = 0; j < (int)(dp[0][i - 1].size()); j++) {
				dp[0][i][0].ss = max(dp[0][i][0].ss, dp[0][i - 1][j].ss + GetPS(i, dp[0][i - 1][j].ff));
			}
			for (int j = 0; j < (int)(dp[1][i - 1].size()); j++) {
				dp[0][i][0].ss = max(dp[0][i][0].ss, dp[1][i - 1][j].ss + GetPS(i, dp[1][i - 1][j].ff));
			}
			dp[1][i][0].ss = dp[0][i][0].ss;
		}
 
		// Case 1: height of i-1 is 0
		// Case 1.1: height of i-2 <= height of i
		// resetoldcur();
		// oldcur[0] = olddp[0][i - 2][0];
		// for (int j = 1; j <= n; j++) {
		// 	oldcur[j] = max(oldcur[j - 1], max(olddp[0][i - 2][j], olddp[1][i - 2][j]));
		// }
		// for (int j = 0; j <= n; j++) {
		// 	olddp[0][i][j] = max(olddp[0][i][j], oldcur[j] + oldps[i - 1][j]);
		// 	olddp[1][i][j] = max(olddp[1][i][j], oldcur[j] + oldps[i - 1][j]);
		// }

		{
			cur.clear();
			for (int j = 0; j < (int)(dp[0][i - 2].size()); j++) {
				cur.pb({dp[0][i - 2][j].ff, max(dp[0][i - 2][j].ss, dp[1][i - 2][j].ss)});
			}
			for (int j = 1; j < (int)(cur.size()); j++) {
				cur[j].ss = max(cur[j].ss, cur[j - 1].ss);
			}
			int ptr = 0, curans = 0;
			for (int j = 0; j < (int)(dp[0][i].size()); j++) {
				while (ptr < (int)(cur.size()) && cur[ptr].ff <= dp[0][i][j].ff) {
					curans = max(curans, cur[ptr].ss);
					ptr++;
				}
				dp[0][i][j].ss = max(dp[0][i][j].ss, curans + GetPS(i - 1, j));
				dp[1][i][j].ss = max(dp[1][i][j].ss, curans + GetPS(i - 1, j));
			}
		}

		// Case 1.2: height of i-2 >= height of i
		// resetoldcur();
		// oldcur[n] = olddp[0][i - 2][n] + oldps[i - 1][n];
		// for (int j = n - 1; j >= 0; j--) {
		// 	oldcur[j] = max(oldcur[j + 1], max(olddp[0][i - 2][j], olddp[1][i - 2][j]) + oldps[i - 1][j]);
		// }
		// for (int j = 0; j <= n; j++) {
		// 	olddp[0][i][j] = max(olddp[0][i][j], oldcur[j]);
		// 	olddp[1][i][j] = max(olddp[1][i][j], oldcur[j]);
		// }

		{
			cur.clear();
			for (int j = 0; j < (int)(dp[0][i - 2].size()); j++) {
				cur.pb({dp[0][i - 2][j].ff, max(dp[0][i - 2][j].ss, dp[1][i - 2][j].ss) + GetPS(i - 1, dp[0][i - 2][j].ff)});
			}
			for (int j = (int)(cur.size()) - 2; j >= 0; j--) {
				cur[j].ss = max(cur[j].ss, cur[j + 1].ss);
			}
			int ptr = (int)(cur.size()) - 1, curans = 0;
			for (int j = (int)(dp[0][i].size()) - 1; j >= 0; j--) {
				while (ptr >= 0 && cur[ptr].ff >= dp[0][i][j].ff) {
					curans = max(curans, cur[ptr].ss);
					ptr--;
				}
				dp[0][i][j].ss = max(dp[0][i][j].ss, curans);
				dp[1][i][j].ss = max(dp[1][i][j].ss, curans);
			}
		}
 
		// now height of i-1 > 0
		// Case 2: height of i-1 <= height of i
		// resetoldcur();
		// oldcur[1] = olddp[0][i - 1][1];
		// for (int j = 2; j <= n; j++) {
		// 	oldcur[j] = max(oldcur[j - 1] + olda[i - 1][j], olddp[0][i - 1][j]);
		// }
		// for (int j = 1; j <= n; j++) {
		// 	olddp[0][i][j] = max(olddp[0][i][j], oldcur[j]);
		// }

		{
			cur.clear();
			int ptr = 1, curans = 0;
			for (int j = 1; j < (int)(dp[0][i].size()); j++) {
				curans += (GetPS(i - 1, dp[0][i][j].ff) - GetPS(i - 1, (j == 1 ? 1 : dp[0][i][j - 1].ff)));
				while (ptr < (int)(dp[0][i - 1].size()) && dp[0][i - 1][ptr].ff <= dp[0][i][j].ff) {
					curans = max(curans, dp[0][i - 1][ptr].ss + (GetPS(i - 1, dp[0][i][j].ff) - GetPS(i - 1, dp[0][i - 1][ptr].ff)));
					ptr++;
				}
				dp[0][i][j].ss = max(dp[0][i][j].ss, curans);
			}
		}
 
		// Case 3: height of i-1 >= height of i
		// resetoldcur();
		// oldcur[n] = max(olddp[0][i - 1][n], olddp[1][i - 1][n]);
		// for (int j = n - 1; j >= 1; j--) {
		// 	oldcur[j] = max(oldcur[j + 1] + olda[i][j + 1], max(olddp[0][i - 1][j], olddp[1][i - 1][j]));
		// }
		// for (int j = 1; j <= n; j++) {
		// 	olddp[1][i][j] = max(olddp[1][i][j], oldcur[j]);
		// }

		{
			cur.clear();
			int ptr = (int)(dp[1][i - 1].size()) - 1, curans = 0;
			for (int j = (int)(dp[1][i].size()) - 1; j >= 1; j--) {
				curans += (GetPS(i, (j + 1 == (int)(dp[1][i].size()) ? n : dp[1][i][j + 1].ff)) - GetPS(i, dp[1][i][j].ff));
				while (ptr >= 0 && dp[1][i - 1][ptr].ff >= dp[0][i][j].ff) {
					curans = max(curans, max(dp[0][i - 1][ptr].ss, dp[1][i - 1][ptr].ss) + (GetPS(i, dp[1][i - 1][ptr].ff) - GetPS(i, dp[1][i][j].ff)));
					ptr--;
				}
				dp[1][i][j].ss = max(dp[1][i][j].ss, curans);
			}
		}
	}
 
	// int ans = max(dp[0][n][0].ss, dp[1][n][0].ss);
	// for (int i = 1; i <= n; i++) {
	// 	// cerr << olddp[0][n][i] << ' ' << olddp[1][n][i] << endl;
	// 	ans = max(ans, max(olddp[0][n][i], olddp[1][n][i]));
	// }
	// return ans;

	// for (int i = 1; i <= n; i++) {
	// 	cerr << i << ": ";
	// 	for (pii &x : dp[1][i]) cerr << "(" << x.ff << ", " << x.ss << ") ";
	// 	cerr << endl;
	// }

	int ans = 0;
	for (pii &x : dp[0][n]) ans = max(ans, x.ss);
	for (pii &x : dp[1][n]) ans = max(ans, x.ss);
	return ans;
}
 
#undef int

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 64784 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '40313049006569'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 640 ms 78056 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40603763492036'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 51836 KB Output is correct
2 Correct 166 ms 51844 KB Output is correct
3 Correct 322 ms 57232 KB Output is correct
4 Correct 264 ms 59056 KB Output is correct
5 Correct 438 ms 74580 KB Output is correct
6 Correct 408 ms 74696 KB Output is correct
7 Correct 399 ms 74584 KB Output is correct
8 Correct 409 ms 74608 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Incorrect 3 ms 820 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '448544935449'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Incorrect 3 ms 820 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '448544935449'
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Incorrect 3 ms 820 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '448544935449'
13 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 51836 KB Output is correct
2 Correct 166 ms 51844 KB Output is correct
3 Correct 322 ms 57232 KB Output is correct
4 Correct 264 ms 59056 KB Output is correct
5 Correct 438 ms 74580 KB Output is correct
6 Correct 408 ms 74696 KB Output is correct
7 Correct 399 ms 74584 KB Output is correct
8 Correct 409 ms 74608 KB Output is correct
9 Correct 496 ms 80776 KB Output is correct
10 Correct 341 ms 44320 KB Output is correct
11 Correct 721 ms 88476 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 164 ms 51924 KB Output is correct
19 Correct 165 ms 51804 KB Output is correct
20 Correct 156 ms 51900 KB Output is correct
21 Correct 166 ms 51896 KB Output is correct
22 Correct 604 ms 91416 KB Output is correct
23 Correct 809 ms 116060 KB Output is correct
24 Correct 814 ms 118584 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 64784 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '40313049006569'
2 Halted 0 ms 0 KB -