Submission #630373

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
630373	2022-08-16T09:38:45 Z	amunduzbaev	Catfish Farm (IOI22_fish)	C++17	35 / 100	1000 ms	114468 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<int> id[N];
int sz[N], pre[N];
ll pref[N][N], suff[N][N], mx[N][N];
ll tmp[N][N], P[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) id[x[i] - 1].push_back(y[i]);
		if(x[i] < n) id[x[i] + 1].push_back(y[i]);
		id[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++){
		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());
	}
	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++){
			pre[j] = lower_bound(id[i - 1].begin(), id[i - 1].end(), id[i][j]) - id[i - 1].begin();
			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]];
				if(k) pref[j][k] = max(pref[j][k], pref[j][k-1]);
				if(k > pre[j]) mx[j][k] = max(mx[j][k-1], mx[j][k]);
			}
			suff[j][sz[i]] = 0;
			for(int k=sz[i]-1;k>=0;k--){
				suff[j][k] = max(suff[j][k+1], suff[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<(int)id[n].size();i++){
		for(int j=0;j<sz[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	Execution timed out	1089 ms	114468 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Execution timed out	1067 ms	111984 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1096 ms	102744 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	3 ms	2644 KB	Output is correct
11	Correct	1 ms	1364 KB	Output is correct
12	Correct	2 ms	2516 KB	Output is correct
13	Correct	1 ms	852 KB	Output is correct
14	Correct	2 ms	2516 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	3 ms	2644 KB	Output is correct
11	Correct	1 ms	1364 KB	Output is correct
12	Correct	2 ms	2516 KB	Output is correct
13	Correct	1 ms	852 KB	Output is correct
14	Correct	2 ms	2516 KB	Output is correct
15	Correct	2 ms	2388 KB	Output is correct
16	Correct	4 ms	2260 KB	Output is correct
17	Correct	239 ms	11948 KB	Output is correct
18	Correct	202 ms	11796 KB	Output is correct
19	Correct	124 ms	11784 KB	Output is correct
20	Correct	103 ms	11780 KB	Output is correct
21	Correct	85 ms	7128 KB	Output is correct
22	Correct	321 ms	13464 KB	Output is correct
23	Correct	26 ms	4704 KB	Output is correct
24	Correct	149 ms	9160 KB	Output is correct
25	Correct	3 ms	2644 KB	Output is correct
26	Correct	25 ms	4308 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	3 ms	2644 KB	Output is correct
11	Correct	1 ms	1364 KB	Output is correct
12	Correct	2 ms	2516 KB	Output is correct
13	Correct	1 ms	852 KB	Output is correct
14	Correct	2 ms	2516 KB	Output is correct
15	Correct	2 ms	2388 KB	Output is correct
16	Correct	4 ms	2260 KB	Output is correct
17	Correct	239 ms	11948 KB	Output is correct
18	Correct	202 ms	11796 KB	Output is correct
19	Correct	124 ms	11784 KB	Output is correct
20	Correct	103 ms	11780 KB	Output is correct
21	Correct	85 ms	7128 KB	Output is correct
22	Correct	321 ms	13464 KB	Output is correct
23	Correct	26 ms	4704 KB	Output is correct
24	Correct	149 ms	9160 KB	Output is correct
25	Correct	3 ms	2644 KB	Output is correct
26	Correct	25 ms	4308 KB	Output is correct
27	Correct	55 ms	71116 KB	Output is correct
28	Execution timed out	1096 ms	45812 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1096 ms	102744 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1089 ms	114468 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #630373

Compilation message