oj.uz

Submission #629289

# Submission time Handle Problem Language Result Execution time Memory
629289 2022-08-14T10:42:53 Z handlename Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 158032 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
vector<pair<int,long long> > arr[100005];
long long qry(int col,int height){ //prefixsum of col to height
	if (arr[col].empty()) return 0;
	pair<int,long long> lol=mp(height,1e18);
	int pos=upper_bound(arr[col].begin(),arr[col].end(),lol)-arr[col].begin();
	pos--;
	return arr[col][pos].second;
}
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]++;
		arr[x[i]].pb(mp(y[i],w[i]));
	}
	for (int i=1;i<=n;i++){
		arr[i].pb(mp(0,0));
		sort(arr[i].begin(),arr[i].end());
		for (int j=1;j<(int)arr[i].size();j++){
			arr[i][j].second+=arr[i][j-1].second;
		}
	}
	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;
		}
		long long maxi=0;
		for (int j=0;j<=n;j++){
			maxi=max(maxi,dp[i-1][j][0]-qry(i,j)-qry(i-1,j));
			if (i>=2){
				maxi=max(maxi,dp[i-2][j][1]-qry(i-1,j));
			}
			dp[i][j][0]=maxi+qry(i-1,j)+qry(i+1,j);
		}
		maxi=0;
		if (i>=2){
			for (int j=n;j>=0;j--){
				maxi=max(maxi,dp[i-2][j][1]);
				dp[i][j][0]=max(dp[i][j][0],maxi+qry(i+1,j));
			}
		}
		maxi=0;
		for (int j=n;j>=0;j--){
			maxi=max(maxi,dp[i-1][j][1]);
			dp[i][j][1]=maxi+qry(i+1,j)-qry(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 1055 ms 27832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Execution timed out 1077 ms 29044 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 1038 ms 21436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2648 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 4 ms 3668 KB Output is correct
10 Correct 7 ms 5332 KB Output is correct
11 Correct 5 ms 3672 KB Output is correct
12 Correct 8 ms 5340 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 10 ms 5348 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2648 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 4 ms 3668 KB Output is correct
10 Correct 7 ms 5332 KB Output is correct
11 Correct 5 ms 3672 KB Output is correct
12 Correct 8 ms 5340 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 10 ms 5348 KB Output is correct
15 Correct 8 ms 5204 KB Output is correct
16 Correct 3 ms 3156 KB Output is correct
17 Correct 42 ms 7244 KB Output is correct
18 Correct 39 ms 7868 KB Output is correct
19 Correct 30 ms 7672 KB Output is correct
20 Correct 34 ms 7644 KB Output is correct
21 Correct 31 ms 7672 KB Output is correct
22 Correct 59 ms 10132 KB Output is correct
23 Correct 16 ms 5756 KB Output is correct
24 Correct 33 ms 6612 KB Output is correct
25 Correct 8 ms 5332 KB Output is correct
26 Correct 18 ms 5716 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2648 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 4 ms 3668 KB Output is correct
10 Correct 7 ms 5332 KB Output is correct
11 Correct 5 ms 3672 KB Output is correct
12 Correct 8 ms 5340 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 10 ms 5348 KB Output is correct
15 Correct 8 ms 5204 KB Output is correct
16 Correct 3 ms 3156 KB Output is correct
17 Correct 42 ms 7244 KB Output is correct
18 Correct 39 ms 7868 KB Output is correct
19 Correct 30 ms 7672 KB Output is correct
20 Correct 34 ms 7644 KB Output is correct
21 Correct 31 ms 7672 KB Output is correct
22 Correct 59 ms 10132 KB Output is correct
23 Correct 16 ms 5756 KB Output is correct
24 Correct 33 ms 6612 KB Output is correct
25 Correct 8 ms 5332 KB Output is correct
26 Correct 18 ms 5716 KB Output is correct
27 Correct 349 ms 143988 KB Output is correct
28 Correct 172 ms 25420 KB Output is correct
29 Correct 772 ms 158032 KB Output is correct
30 Execution timed out 1086 ms 126292 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1038 ms 21436 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 1055 ms 27832 KB Time limit exceeded
2 Halted 0 ms 0 KB -