oj.uz

Submission #737050

# Submission time Handle Problem Language Result Execution time Memory
737050 2023-05-06T13:55:54 Z minhcool Catfish Farm (IOI22_fish) C++17
52 / 100
 318 ms 296724 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
//#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, m;
 
long long val[3005][3005], pref[3005][3005];
 
// dp[row_i][row_j][i - 1 > or = or <]
long long dp[3005][3005][2];
 
ll x[N], y[N], w[N];
 
ll solve1(){
	ll tol = 0;
	for(int i = 1; i <= m; i++) tol += w[i];
	return tol;
}
 
map<ii, ll> mp;
 
ll solve2(){
	for(int i = 1; i <= m; i++) mp[{x[i], y[i]}] = w[i];
	if(n >= 3){
		ll mx = -1, total = 0;
		for(int i = 1; i <= n; i++) total += mp[{2, i}];
		mx = total;
		for(int i = 1; i <= n; i++){
			total += (mp[{1, i}] - mp[{2, i}]);
			mx = max(mx, total);
		}
		return mx;
	}
	else{
		return max(mp[{1, 1}] + mp[{1, 2}], mp[{2, 1}] + mp[{2, 2}]);
	}
}
 
ll dp1[N][2][2];
 
ll solve3(){
	//cout << "OK\n";
	for(int i = 1; i <= m; i++) mp[{x[i], y[i]}] = w[i];
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 2; j++){
			for(int k = 0; k < 2; k++) dp1[i][j][k] = -oo;
		}
	}
	dp1[1][0][0] = dp1[1][1][0] = 0;
	for(int i = 2; i <= (n + 1); i++){
		for(int j = 0; j < 2; j++){
			if(i == (n + 1) && j) break;
			for(int k = 0; k < 2; k++){
				for(int h = 0; h < 2; h++){
					dp1[i][j][k] = max(dp1[i][j][k], dp1[i - 1][k][h] + mp[{i - 1, 1}] * (!k && (j | h)));
				}
				//cout << i << " " << j << " " << k << " " << dp1[i][j][k] << "\n";
			}
		}
	}
	return max(dp1[n + 1][0][0], dp1[n + 1][0][1]);
}
 
 
long long max_weights(int _n, int _m, vector<int> _x, vector<int> _y, vector<int> _w){
	n = _n, m = _m;
	bool chk1 = 1, chk2 = 1, chk3 = 1;
	for(int i = 0; i < m; i++){
		x[i + 1] = _x[i] + 1, y[i + 1] = _y[i] + 1, w[i + 1] = _w[i];
		chk1 &= (!(_x[i] & 1));
		chk2 &= (x[i] <= 1);
		chk3 &= (y[i] <= 0);
		val[_x[i] + 1][_y[i] + 1] += (long long)_w[i];
	}
	if(n <= 3000){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++) pref[i][j] = pref[i][j - 1] + val[i][j];
		}
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				dp[i][j][0] = dp[i][j][1] = -oo;
			}
		}
		//dp[0][0][0] = 0;
		//15206896898496
		for(int i = 0; i <= n; i++){
			//dp[2][i][0] = pref[1][i];// 0 -> <=
			//dp[2][i][1] = pref[2][i;
			dp[1][i][0] = 0;
		}
		for(int i = 2; i <= n + 1; i++){
			// calculate (i - 1)
			long long maximum = -oo;
			for(int nxt = 0; nxt <= n; nxt++){
				maximum = max(maximum, dp[i - 1][nxt][0] - pref[i - 1][nxt]);
				dp[i][nxt][0] = max(dp[i][nxt][0], maximum + pref[i - 1][nxt]);
			}
			maximum = -oo;
			for(int nxt = n; nxt >= 0; nxt--){
				dp[i][nxt][1] = max(dp[i][nxt][1], maximum - pref[i][nxt]);
				maximum = max(maximum, dp[i - 1][nxt][1] + pref[i][nxt]);
			}
			for(int lst = 0; lst <= n; lst++){
				// 0 - 0
				/*
				for(int nxt = lst; nxt <= n; nxt++){
					dp[i][nxt][0] = max(dp[i][nxt][0], dp[i - 1][lst][0] + (pref[i - 1][nxt] - pref[i - 1][lst]));
				}
				// 1 - 1
				for(int nxt = lst - 1; nxt >= 0; nxt--){
					dp[i][nxt][1] = max(dp[i][nxt][1], dp[i - 1][lst][1] + pref[i][lst] - pref[i][nxt]);	
				}*/
				// 0 - 1
				if(lst == n){
					for(int nxt = 0; nxt < n; nxt++) dp[i][nxt][1] = max(dp[i][nxt][1], dp[i - 1][n][0] + pref[i][n] - pref[i][nxt]);
				}
				// 1 - 0
				if(!lst){
					dp[i][0][0] = max(dp[i][0][0], dp[i - 1][0][1]);
					for(int nxt = 1; nxt <= n; nxt++) dp[i][nxt][0] = max(dp[i][nxt][0], max(dp[i - 1][0][0] + pref[i - 1][nxt], dp[i - 1][0][1]));
				}
			}
		}
		return max(dp[n + 1][0][0], dp[n + 1][0][1]);
	}
	else if(chk1) return solve1();
	else if(chk2) return solve2();
	else if(chk3) return solve3();
}
 
/*
void process(){
	int n, m;
	vector<int> a, b, c;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x, y, z;
		cin >> x >> y >> z;
		a.pb(x), b.pb(y), c.pb(z);
	}
	cout << max_weights(n, m, a, b, c) << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	freopen("fish.inp", "r", stdin);
	//freopen("fish.out", "w", stdout);
	//cout << "OK\n";
	//return 0;
	process();
}
*/

Compilation message

fish.cpp:17:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   17 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:143:1: warning: control reaches end of non-void function [-Wreturn-type]
  143 | }
      | ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5452 KB Output is correct
2 Correct 30 ms 6268 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 132 ms 15160 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 223 ms 27916 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '851126173'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Runtime error 5 ms 408 KB Execution killed with signal 11
3 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 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 5 ms 6228 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 4 ms 6100 KB Output is correct
13 Correct 1 ms 1336 KB Output is correct
14 Correct 4 ms 6100 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 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 5 ms 6228 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 4 ms 6100 KB Output is correct
13 Correct 1 ms 1336 KB Output is correct
14 Correct 4 ms 6100 KB Output is correct
15 Correct 4 ms 5996 KB Output is correct
16 Correct 2 ms 1328 KB Output is correct
17 Correct 17 ms 8532 KB Output is correct
18 Correct 23 ms 8396 KB Output is correct
19 Correct 18 ms 8916 KB Output is correct
20 Correct 17 ms 8844 KB Output is correct
21 Correct 16 ms 8916 KB Output is correct
22 Correct 29 ms 11788 KB Output is correct
23 Correct 6 ms 7252 KB Output is correct
24 Correct 12 ms 8516 KB Output is correct
25 Correct 4 ms 6100 KB Output is correct
26 Correct 6 ms 6868 KB Output is correct

Subtask #6
17.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 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 5 ms 6228 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 4 ms 6100 KB Output is correct
13 Correct 1 ms 1336 KB Output is correct
14 Correct 4 ms 6100 KB Output is correct
15 Correct 4 ms 5996 KB Output is correct
16 Correct 2 ms 1328 KB Output is correct
17 Correct 17 ms 8532 KB Output is correct
18 Correct 23 ms 8396 KB Output is correct
19 Correct 18 ms 8916 KB Output is correct
20 Correct 17 ms 8844 KB Output is correct
21 Correct 16 ms 8916 KB Output is correct
22 Correct 29 ms 11788 KB Output is correct
23 Correct 6 ms 7252 KB Output is correct
24 Correct 12 ms 8516 KB Output is correct
25 Correct 4 ms 6100 KB Output is correct
26 Correct 6 ms 6868 KB Output is correct
27 Correct 190 ms 224368 KB Output is correct
28 Correct 90 ms 33612 KB Output is correct
29 Correct 250 ms 229596 KB Output is correct
30 Correct 271 ms 272412 KB Output is correct
31 Correct 264 ms 272784 KB Output is correct
32 Correct 87 ms 30416 KB Output is correct
33 Correct 318 ms 296708 KB Output is correct
34 Correct 290 ms 296724 KB Output is correct
35 Correct 218 ms 232612 KB Output is correct
36 Correct 316 ms 242544 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Runtime error 5 ms 408 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5452 KB Output is correct
2 Correct 30 ms 6268 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Runtime error 132 ms 15160 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -