Submission #630371

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
630371	2022-08-16T09:34:28 Z	amunduzbaev	Catfish Farm (IOI22_fish)	C++17	35 / 100	1000 ms	160452 KB

fish

#include "fish.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

#ifndef EVAL
#include "grader.cpp"
#endif

const int N = 3005;
vector<ll> dp[N], id[N];
ll P[N][N], sz[N], tmp[N][N], pre[N];
ll pref[N][N], suff[N][N], mx[N][N];

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]++;
		if(x[i] > 1) dp[x[i] - 1].push_back(y[i]);
		if(x[i] < n) dp[x[i] + 1].push_back(y[i]);
		dp[x[i]].push_back(y[i]);
		P[x[i]][y[i]] += w[i];
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			P[i][j] += P[i][j-1];
		}
	}
	
	for(int i=0;i<N;i++){
		swap(id[i], dp[i]);
		id[i].push_back(0);
		sort(id[i].begin(), id[i].end());
		id[i].erase(unique(id[i].begin(), id[i].end()), id[i].end());
		dp[i].resize(id[i].size());
	}
	sz[0] = 1;
	
	for(int i=1;i<=n;i++){
		int j_ = 0;
		for(auto j : id[i]){
			int pos, p2;
			if(i > 1){
				pos = lower_bound(id[i-2].begin(), id[i-2].end(), j) - id[i-2].begin();
				p2 = upper_bound(id[i-2].begin(), id[i-2].end(), j) - id[i-2].begin();
			} else {
				pos = 0;
				p2 = 1;
			}
			int k_ = 0;
			for(auto k : id[i-1]){
				tmp[j_][k_] = 0;
				if(j <= k){
					tmp[j_][k_] = max(tmp[j_][k_], pref[k_][sz[i-1] - 1] + P[i-1][j] + P[i+1][j] - (i > 1 ? P[i][j] : 0) - P[i-1][j]);
				} else {
					tmp[j_][k_] = max(tmp[j_][k_], pref[k_][pre[k_] - 1] + P[i-1][j] + P[i+1][j] - (i > 1 ? P[i][k] : 0) - P[i-1][k]);
					if(pos < sz[i-1]) tmp[j_][k_] = max(tmp[j_][k_], suff[k_][pos] + P[i-1][j] + P[i+1][j] - (i > 1 ? P[i][k] : 0) - P[i-1][j]);
					if(p2) tmp[j_][k_] = max(tmp[j_][k_], mx[k_][p2 - 1] + P[i-1][j] + P[i+1][j] - (i > 1 ? P[i][k] : 0));
				}
				k_++;
			}
			j_++;
		}
 		sz[i] = id[i-1].size();
		
		for(int j=0;j<(int)id[i].size();j++){
			suff[j][sz[i]] = 0;
			for(int k=0;k<sz[i];k++){
				pref[j][k] = suff[j][k] = mx[j][k] = tmp[j][k];
				mx[j][k] -= P[i][id[i-1][k]];
			}
			for(int k=1;k<sz[i];k++){
				pref[j][k] = max(pref[j][k], pref[j][k - 1]);
			}
			for(int k=sz[i]-1;k>=0;k--){
				suff[j][k] = max(suff[j][k+1], suff[j][k]);
			}
			
			pre[j] = lower_bound(id[i - 1].begin(), id[i - 1].end(), id[i][j]) - id[i - 1].begin();
			for(int k=pre[j] + 1;k<sz[i];k++){
				mx[j][k] = max(mx[j][k-1], mx[j][k]);
			}
			pre[j] = upper_bound(id[i - 1].begin(), id[i - 1].end(), id[i][j]) - id[i - 1].begin();
		}
	}
	
	ll res = 0;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			res = max(res, tmp[i][j]);
		}
	}
	
	return res;
}

/*

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

5 6
2 3 3
2 1 2
4 1 3
2 0 10
4 4 1
4 0 7

*/

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	739 ms	151252 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	724 KB	Output is correct
2	Runtime error	781 ms	160452 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	782 ms	143912 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	724 KB	Output is correct
2	Correct	1 ms	724 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	1 ms	1492 KB	Output is correct
10	Correct	4 ms	2776 KB	Output is correct
11	Correct	2 ms	1620 KB	Output is correct
12	Correct	3 ms	2772 KB	Output is correct
13	Correct	2 ms	980 KB	Output is correct
14	Correct	3 ms	2716 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	724 KB	Output is correct
2	Correct	1 ms	724 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	1 ms	1492 KB	Output is correct
10	Correct	4 ms	2776 KB	Output is correct
11	Correct	2 ms	1620 KB	Output is correct
12	Correct	3 ms	2772 KB	Output is correct
13	Correct	2 ms	980 KB	Output is correct
14	Correct	3 ms	2716 KB	Output is correct
15	Correct	2 ms	2644 KB	Output is correct
16	Correct	8 ms	2516 KB	Output is correct
17	Correct	329 ms	13960 KB	Output is correct
18	Correct	278 ms	13716 KB	Output is correct
19	Correct	180 ms	13588 KB	Output is correct
20	Correct	145 ms	13516 KB	Output is correct
21	Correct	128 ms	8956 KB	Output is correct
22	Correct	466 ms	16520 KB	Output is correct
23	Correct	36 ms	5244 KB	Output is correct
24	Correct	215 ms	10696 KB	Output is correct
25	Correct	3 ms	2900 KB	Output is correct
26	Correct	27 ms	4812 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	724 KB	Output is correct
2	Correct	1 ms	724 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	1 ms	1492 KB	Output is correct
10	Correct	4 ms	2776 KB	Output is correct
11	Correct	2 ms	1620 KB	Output is correct
12	Correct	3 ms	2772 KB	Output is correct
13	Correct	2 ms	980 KB	Output is correct
14	Correct	3 ms	2716 KB	Output is correct
15	Correct	2 ms	2644 KB	Output is correct
16	Correct	8 ms	2516 KB	Output is correct
17	Correct	329 ms	13960 KB	Output is correct
18	Correct	278 ms	13716 KB	Output is correct
19	Correct	180 ms	13588 KB	Output is correct
20	Correct	145 ms	13516 KB	Output is correct
21	Correct	128 ms	8956 KB	Output is correct
22	Correct	466 ms	16520 KB	Output is correct
23	Correct	36 ms	5244 KB	Output is correct
24	Correct	215 ms	10696 KB	Output is correct
25	Correct	3 ms	2900 KB	Output is correct
26	Correct	27 ms	4812 KB	Output is correct
27	Correct	67 ms	71544 KB	Output is correct
28	Execution timed out	1010 ms	52056 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	782 ms	143912 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	739 ms	151252 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Submission #630371

Compilation message