oj.uz

Submission #684933

# Submission time Handle Problem Language Result Execution time Memory
684933 2023-01-22T21:15:01 Z Konti2 Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 78076 KB 
#include <bits/stdc++.h>
#include "fish.h"

using namespace std;

using ll = long long;

ll t[3001][3001];
ll dp[3001][3001][2];
ll sum[3001][3001];

ll max_weights(int N, int M, vector<int> x, vector<int> y, vector<int> w){
	  ll ans = 0;
	  for (int i = 0; i < M; i++){
		  t[x[i]][y[i]] = w[i];
	  }
	  for (int i = 0; i < N; i++){
		  for (int h = 1; h <= N; h++){
			  sum[i][h] = t[i][h-1] + sum[i][h-1];
		  }
		  if (i){
			  // CASE 1 a >= b
			  dp[i][0][1] = dp[i-1][0][1];
			  ans = max(ans, dp[i][0][1]);
			  for (int a = 1; a <= N; a++){
				  dp[i][a][1] = max(dp[i-1][a][1], dp[i][a-1][1] + t[i-1][a-1]);
				  ans = max(ans, dp[i][a][1]);
			  }
			  // CASE 2 b >= a;
			  dp[i][N][0] = max(dp[i-1][N][0], dp[i-1][N][1]);
			  ans = max(ans, dp[i][N][0]);
			  for (int a = N-1; a >= 0; a--){
				  dp[i][a][0] = max(dp[i][a+1][0] + t[i][a], max(dp[i-1][a][0], dp[i-1][a][1]));
				   ans = max(ans, dp[i][a][0]);
			  }
			  if (i-1){
				// CASE 3 min(a,b,c) == b == 0 && a >= c
				dp[i][0][1] = max(dp[i][0][1], max(dp[i-2][0][1], dp[i-2][0][0]));
				ans = max(ans, dp[i][0][1]);
				for (int a = 1; a <= N; a++){
					dp[i][a][1] = max(dp[i][a][1], max(dp[i][a-1][1] + t[i-1][a-1], max(dp[i-2][a][0], dp[i-2][a][1]) + sum[i-1][a]));
					 ans = max(ans, dp[i][a][1]);
				}
				// CASE 4 min(a,b,c) == b == 0 && c >= a;
				dp[i][N][1] = max(dp[i][N][1], max(dp[i-2][N][1], dp[i-2][N][0]) + sum[i-1][N]);
				ans = max(ans, dp[i][N][1]);
				for (int a = N-1; a >= 0; a--){
					dp[i][a][1] = max(dp[i][a][1], max(dp[i][a+1][1], max(dp[i-2][a][0], dp[i-2][a][1]) + sum[i-1][a]));
					 ans = max(ans, dp[i][a][1]);
				}
			}
		}
	}
			  
			  
						  
	  
	  return ans;
  }
	
	
/*int main(){
	int n;
	cin >> n;
	int m;
	cin >> m;
	vector<int> x(m);
	vector<int> y(m);
	vector<int> w(m);
	for (int i = 0; i < m; i++){
		cin >> x[i];
		cin >> y[i];
		cin >> w[i];
	}
	cout << max_weights(n, m, x, y, w);
	return 0;
}

*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 78076 KB Time limit exceeded
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 Execution timed out 1085 ms 77492 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 1089 ms 70096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 2 ms 2644 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '308748060723'
10 Halted 0 ms 0 KB -

Subtask #5
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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 2 ms 2644 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '308748060723'
10 Halted 0 ms 0 KB -

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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 2 ms 2644 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '308748060723'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 70096 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 1090 ms 78076 KB Time limit exceeded
2 Halted 0 ms 0 KB -