oj.uz

Submission #629246

# Submission time Handle Problem Language Result Execution time Memory
629246 2022-08-14T10:00:59 Z handlename Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 118688 KB 
#include <bits/stdc++.h>
//#include "fish.h"
using namespace std;
#define pb push_back
#define mp make_pair
long long dp[3005][3005][2]; //col,height,increasing/decreasing
long long pre[3005][3005];
long long 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]++;
		pre[x[i]][y[i]]=w[i];
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			pre[i][j]+=pre[i][j-1];
		}
	}
	for (int i=1;i<=n;i++){ //col
		for (int j=0;j<=n;j++){ //col height
			dp[i][j][0]=-1e18;
			dp[i][j][1]=-1e18;
			//calculate increasing
			for (int k=0;k<=j;k++){ //prev col height
				long long cur=dp[i-1][k][0];
				cur-=pre[i][k]+pre[i-1][k];
				dp[i][j][0]=max(dp[i][j][0],cur);
			}
			if (i>=2){
				//i-1 col height is 0
				for (int k=0;k<=j;k++){ //i-2 col height
					long long cur=dp[i-2][k][1];
					cur-=pre[i-1][k];
					dp[i][j][0]=max(dp[i][j][0],cur);
				}
				for (int k=j;k<=n;k++){ //i-2 col height
					long long cur=dp[i-2][k][1];
					cur-=pre[i-1][j];
					dp[i][j][0]=max(dp[i][j][0],cur);
				}
			}
			dp[i][j][0]+=pre[i-1][j]+pre[i+1][j];
			//calculate decreasing
			for (int k=j;k<=n;k++){ //prev col height
				dp[i][j][1]=max(dp[i][j][1],dp[i-1][k][1]);
			}
			dp[i][j][1]+=pre[i+1][j]-pre[i][j];
		}
		for (int j=0;j<=n;j++){
			dp[i][j][1]=max(dp[i][j][1],dp[i][j][0]);
		}
	}
	long long ans=0;
	for (int j=0;j<=n;j++){
		ans=max(ans,dp[n][j][1]);
	}
	return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 118688 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 1101 ms 116736 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 1079 ms 107016 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 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 8 ms 2004 KB Output is correct
10 Correct 72 ms 4944 KB Output is correct
11 Correct 11 ms 2072 KB Output is correct
12 Correct 74 ms 4816 KB Output is correct
13 Correct 2 ms 980 KB Output is correct
14 Correct 62 ms 4980 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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 8 ms 2004 KB Output is correct
10 Correct 72 ms 4944 KB Output is correct
11 Correct 11 ms 2072 KB Output is correct
12 Correct 74 ms 4816 KB Output is correct
13 Correct 2 ms 980 KB Output is correct
14 Correct 62 ms 4980 KB Output is correct
15 Correct 61 ms 4780 KB Output is correct
16 Correct 2 ms 1092 KB Output is correct
17 Correct 76 ms 5996 KB Output is correct
18 Correct 71 ms 5980 KB Output is correct
19 Correct 70 ms 6000 KB Output is correct
20 Correct 76 ms 5996 KB Output is correct
21 Correct 75 ms 5952 KB Output is correct
22 Correct 86 ms 6980 KB Output is correct
23 Correct 61 ms 5064 KB Output is correct
24 Correct 67 ms 5636 KB Output is correct
25 Correct 59 ms 4820 KB Output is correct
26 Correct 67 ms 5084 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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 8 ms 2004 KB Output is correct
10 Correct 72 ms 4944 KB Output is correct
11 Correct 11 ms 2072 KB Output is correct
12 Correct 74 ms 4816 KB Output is correct
13 Correct 2 ms 980 KB Output is correct
14 Correct 62 ms 4980 KB Output is correct
15 Correct 61 ms 4780 KB Output is correct
16 Correct 2 ms 1092 KB Output is correct
17 Correct 76 ms 5996 KB Output is correct
18 Correct 71 ms 5980 KB Output is correct
19 Correct 70 ms 6000 KB Output is correct
20 Correct 76 ms 5996 KB Output is correct
21 Correct 75 ms 5952 KB Output is correct
22 Correct 86 ms 6980 KB Output is correct
23 Correct 61 ms 5064 KB Output is correct
24 Correct 67 ms 5636 KB Output is correct
25 Correct 59 ms 4820 KB Output is correct
26 Correct 67 ms 5084 KB Output is correct
27 Execution timed out 1086 ms 73504 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 107016 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 1078 ms 118688 KB Time limit exceeded
2 Halted 0 ms 0 KB -