oj.uz

Submission #630232

# Submission time Handle Problem Language Result Execution time Memory
630232 2022-08-16T06:35:16 Z amunduzbaev Catfish Farm (IOI22_fish) C++17
35 / 100
 382 ms 10100 KB 
#include "fish.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

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

const int N = 305;
//~ vector<ll> dp[N], pref[N], suff[N], mx[N], id[N];
ll P[N][N], sz[N];
ll dp[N][N], pref[N][N], suff[N][N], mx[N][N];
ll tmp[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());
		//~ dp[i].resize(id[i].size());
	//~ }
	
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n;k++){
				tmp[j][k] = 0;
				if(j <= k){
					tmp[j][k] = max(tmp[j][k], pref[k][n] + 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][k] + P[i-1][j] + P[i+1][j] - (i > 1 ? P[i][k] : 0) - P[i-1][k]);
					tmp[j][k] = max(tmp[j][k], suff[k][j] + P[i-1][j] + P[i+1][j] - (i > 1 ? P[i][k] : 0) - P[i-1][j]);
					tmp[j][k] = max(tmp[j][k], mx[k][j] + P[i-1][j] + P[i+1][j] - (i > 1 ? P[i][k] : 0));
				}
				dp[i][j] = max(dp[i][j], tmp[j][k]);
			}
		}
		
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n;k++){
				pref[j][k] = suff[j][k] = mx[j][k] = tmp[j][k];
				mx[j][k] -= P[i][k];
			}
			for(int k=1;k<=n;k++){
				pref[j][k] = max(pref[j][k], pref[j][k - 1]);
			}
			for(int k=n-1;~k;k--){
				suff[j][k] = max(suff[j][k+1], suff[j][k]);
			}
			for(int k=j+1;k<=n;k++){
				mx[j][k] = max(mx[j][k-1], mx[j][k]);
			}
		}
	}
	
	ll res = 0;
	for(int j=0;j<=n;j++){
		res = max(res, dp[n][j]);
	}
	
	return res;
}

/*

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

*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 6168 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 0 ms 340 KB Output is correct
2 Runtime error 57 ms 10100 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 2 ms 1876 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 46 ms 2428 KB Output is correct
10 Correct 342 ms 4544 KB Output is correct
11 Correct 51 ms 2476 KB Output is correct
12 Correct 331 ms 4636 KB Output is correct
13 Correct 6 ms 1396 KB Output is correct
14 Correct 328 ms 4520 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 46 ms 2428 KB Output is correct
10 Correct 342 ms 4544 KB Output is correct
11 Correct 51 ms 2476 KB Output is correct
12 Correct 331 ms 4636 KB Output is correct
13 Correct 6 ms 1396 KB Output is correct
14 Correct 328 ms 4520 KB Output is correct
15 Correct 331 ms 4536 KB Output is correct
16 Correct 6 ms 1364 KB Output is correct
17 Correct 348 ms 6092 KB Output is correct
18 Correct 375 ms 6040 KB Output is correct
19 Correct 345 ms 6228 KB Output is correct
20 Correct 373 ms 6100 KB Output is correct
21 Correct 335 ms 6028 KB Output is correct
22 Correct 382 ms 7100 KB Output is correct
23 Correct 328 ms 4872 KB Output is correct
24 Correct 339 ms 5664 KB Output is correct
25 Correct 357 ms 4588 KB Output is correct
26 Correct 331 ms 5012 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 46 ms 2428 KB Output is correct
10 Correct 342 ms 4544 KB Output is correct
11 Correct 51 ms 2476 KB Output is correct
12 Correct 331 ms 4636 KB Output is correct
13 Correct 6 ms 1396 KB Output is correct
14 Correct 328 ms 4520 KB Output is correct
15 Correct 331 ms 4536 KB Output is correct
16 Correct 6 ms 1364 KB Output is correct
17 Correct 348 ms 6092 KB Output is correct
18 Correct 375 ms 6040 KB Output is correct
19 Correct 345 ms 6228 KB Output is correct
20 Correct 373 ms 6100 KB Output is correct
21 Correct 335 ms 6028 KB Output is correct
22 Correct 382 ms 7100 KB Output is correct
23 Correct 328 ms 4872 KB Output is correct
24 Correct 339 ms 5664 KB Output is correct
25 Correct 357 ms 4588 KB Output is correct
26 Correct 331 ms 5012 KB Output is correct
27 Runtime error 2 ms 468 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1876 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 32 ms 6168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -