oj.uz

Submission #737049

# Submission time Handle Problem Language Result Execution time Memory
737049 2023-05-06T13:54:45 Z minhcool Catfish Farm (IOI22_fish) C++17
52 / 100
 287 ms 290292 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 = 3e3 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, m;

long long val[N][N], pref[N][N];

// dp[row_i][row_j][i - 1 > or = or <]
long long dp[N][N][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 23 ms 3828 KB Output is correct
2 Correct 28 ms 5952 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Runtime error 95 ms 21096 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 308 KB Output is correct
2 Runtime error 122 ms 36216 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 5 ms 340 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 312 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 340 KB Output is correct
5 Correct 0 ms 308 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 312 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 1364 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 312 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 340 KB Output is correct
5 Correct 0 ms 308 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 312 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 1364 KB Output is correct
14 Correct 4 ms 6100 KB Output is correct
15 Correct 4 ms 6100 KB Output is correct
16 Correct 2 ms 1364 KB Output is correct
17 Correct 15 ms 7516 KB Output is correct
18 Correct 16 ms 7448 KB Output is correct
19 Correct 17 ms 7888 KB Output is correct
20 Correct 17 ms 7884 KB Output is correct
21 Correct 16 ms 7892 KB Output is correct
22 Correct 31 ms 9680 KB Output is correct
23 Correct 6 ms 7124 KB Output is correct
24 Correct 12 ms 7824 KB Output is correct
25 Correct 4 ms 6100 KB Output is correct
26 Correct 6 ms 6740 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 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 340 KB Output is correct
5 Correct 0 ms 308 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 312 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 1364 KB Output is correct
14 Correct 4 ms 6100 KB Output is correct
15 Correct 4 ms 6100 KB Output is correct
16 Correct 2 ms 1364 KB Output is correct
17 Correct 15 ms 7516 KB Output is correct
18 Correct 16 ms 7448 KB Output is correct
19 Correct 17 ms 7888 KB Output is correct
20 Correct 17 ms 7884 KB Output is correct
21 Correct 16 ms 7892 KB Output is correct
22 Correct 31 ms 9680 KB Output is correct
23 Correct 6 ms 7124 KB Output is correct
24 Correct 12 ms 7824 KB Output is correct
25 Correct 4 ms 6100 KB Output is correct
26 Correct 6 ms 6740 KB Output is correct
27 Correct 180 ms 224328 KB Output is correct
28 Correct 76 ms 30080 KB Output is correct
29 Correct 263 ms 222980 KB Output is correct
30 Correct 271 ms 265648 KB Output is correct
31 Correct 274 ms 266604 KB Output is correct
32 Correct 99 ms 25840 KB Output is correct
33 Correct 270 ms 290292 KB Output is correct
34 Correct 287 ms 290268 KB Output is correct
35 Correct 208 ms 230436 KB Output is correct
36 Correct 261 ms 236020 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 5 ms 340 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 23 ms 3828 KB Output is correct
2 Correct 28 ms 5952 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Runtime error 95 ms 21096 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -