oj.uz

Submission #763896

# Submission time Handle Problem Language Result Execution time Memory
763896 2023-06-23T02:41:02 Z OrazB Catfish Farm (IOI22_fish) C++17
53 / 100
 864 ms 2097152 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
//Dijkstra->set
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 100005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <ll, ll>
#define pb push_back
#define ff first
#define ss second

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
	bool sub1 = 0, sub2 = 0;
	ll sum = 0, sum1 = 0, sum2 = 0;
	vector<pii> col1, col2;
	for (int i = 0; i < m; i++){
		sub1 |= (x[i]%2);
		sub2 |= (x[i]>1);
		sum += w[i];
		if (!x[i]) col1.pb({y[i], w[i]}), sum1 += w[i];
		else col2.pb({y[i], w[i]}), sum2 += w[i];
	}
	if (!sub1) return sum;
	if (!sub2){
		if (n == 2) return max(sum1, sum2);
		sort(all(col1)); sort(all(col2));
		ll mx = sum2;
		int pos = 0;
		for (auto i : col1){
			while(pos < (int)col2.size() and col2[pos].ff <= i.ff){
				sum2 -= col2[pos].ss;
				pos++;
			}
			sum2 += i.ss;
			mx = max(mx, sum2);
		}
		return mx;
	}
	int nn = *max_element(all(y))+1;
	vector<vector<ll>> a(n+2, vector<ll> (nn+2, 0));
	for (int i = 0; i < m; i++){
		a[x[i]+1][y[i]+1] = w[i];
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= nn; j++){
			a[i][j] += a[i][j-1];
		}
	}
	vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(nn+1, vector<ll>(nn+1, 0)));
	vector<vector<ll>> pref(nn+1, vector<ll>(nn+1, 0)), suff(nn+1, vector<ll>(nn+1, 0));
	ll ans = 0;
	for (int i = 2; i <= n; i++){
		for (int j = 0; j <= nn; j++){
			for (int k = 0; k <= nn; k++){
				if (k <= j){
					dp[i][j][k] = max(pref[k][j]+(a[i-1][j]-a[i-1][k]), suff[k][j]);
				}else{
					dp[i][j][k] = max(dp[i][j][k], suff[k][0]+a[i][k]-a[i][j]);
				}
				if (i == n) ans = max(ans, dp[i][j][k]);
			}
		}
		for (int j = 0; j <= nn; j++){
			pref[j][0] = dp[i][j][0];
			for (int k = 1; k <= nn; k++){
				pref[j][k] = max(pref[j][k-1], dp[i][j][k]-(k>j ? a[i][k]-a[i][j] : 0));
			}
			suff[j][nn] = dp[i][j][nn];
			for (int k = nn-1; k >= 0; k--) suff[j][k] = max(suff[j][k+1], dp[i][j][k]);
		}
	}
	return ans;
}

// int main ()
// {
// 	int n, m;
// 	cin >> n >> m;
// 	vector<int> x(m), y(m), w(m);
// 	for (int i = 0; i < m; i++) cin >> x[i] >> y[i] >> w[i];
// 	cout << max_weights(n,m,x,y,w);
// }

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5680 KB Output is correct
2 Correct 25 ms 6580 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 82 ms 20944 KB Output is correct
6 Correct 80 ms 20876 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 53 ms 10032 KB Output is correct
3 Correct 63 ms 11712 KB Output is correct
4 Correct 20 ms 5700 KB Output is correct
5 Correct 25 ms 6580 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 25 ms 5712 KB Output is correct
13 Correct 32 ms 6576 KB Output is correct
14 Correct 30 ms 5236 KB Output is correct
15 Correct 29 ms 5748 KB Output is correct
16 Correct 26 ms 5340 KB Output is correct
17 Correct 29 ms 5688 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 24 ms 20640 KB Output is correct
3 Correct 35 ms 21608 KB Output is correct
4 Correct 34 ms 22700 KB Output is correct
5 Correct 51 ms 26132 KB Output is correct
6 Correct 45 ms 25464 KB Output is correct
7 Correct 48 ms 26016 KB Output is correct
8 Correct 49 ms 26032 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 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 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 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 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 265 ms 217936 KB Output is correct
16 Correct 5 ms 4188 KB Output is correct
17 Correct 270 ms 221228 KB Output is correct
18 Correct 270 ms 221300 KB Output is correct
19 Correct 268 ms 221296 KB Output is correct
20 Correct 265 ms 221320 KB Output is correct
21 Correct 78 ms 58692 KB Output is correct
22 Correct 289 ms 223744 KB Output is correct
23 Correct 269 ms 219276 KB Output is correct
24 Correct 263 ms 220456 KB Output is correct
25 Correct 2 ms 1620 KB Output is correct
26 Correct 257 ms 219240 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 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 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 265 ms 217936 KB Output is correct
16 Correct 5 ms 4188 KB Output is correct
17 Correct 270 ms 221228 KB Output is correct
18 Correct 270 ms 221300 KB Output is correct
19 Correct 268 ms 221296 KB Output is correct
20 Correct 265 ms 221320 KB Output is correct
21 Correct 78 ms 58692 KB Output is correct
22 Correct 289 ms 223744 KB Output is correct
23 Correct 269 ms 219276 KB Output is correct
24 Correct 263 ms 220456 KB Output is correct
25 Correct 2 ms 1620 KB Output is correct
26 Correct 257 ms 219240 KB Output is correct
27 Runtime error 864 ms 2097152 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 24 ms 20640 KB Output is correct
3 Correct 35 ms 21608 KB Output is correct
4 Correct 34 ms 22700 KB Output is correct
5 Correct 51 ms 26132 KB Output is correct
6 Correct 45 ms 25464 KB Output is correct
7 Correct 48 ms 26016 KB Output is correct
8 Correct 49 ms 26032 KB Output is correct
9 Runtime error 627 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5680 KB Output is correct
2 Correct 25 ms 6580 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 82 ms 20944 KB Output is correct
6 Correct 80 ms 20876 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 53 ms 10032 KB Output is correct
9 Correct 63 ms 11712 KB Output is correct
10 Correct 20 ms 5700 KB Output is correct
11 Correct 25 ms 6580 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 25 ms 5712 KB Output is correct
19 Correct 32 ms 6576 KB Output is correct
20 Correct 30 ms 5236 KB Output is correct
21 Correct 29 ms 5748 KB Output is correct
22 Correct 26 ms 5340 KB Output is correct
23 Correct 29 ms 5688 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 24 ms 20640 KB Output is correct
26 Correct 35 ms 21608 KB Output is correct
27 Correct 34 ms 22700 KB Output is correct
28 Correct 51 ms 26132 KB Output is correct
29 Correct 45 ms 25464 KB Output is correct
30 Correct 48 ms 26016 KB Output is correct
31 Correct 49 ms 26032 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 1 ms 300 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 724 KB Output is correct
42 Correct 1 ms 468 KB Output is correct
43 Correct 1 ms 596 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 1 ms 468 KB Output is correct
46 Correct 265 ms 217936 KB Output is correct
47 Correct 5 ms 4188 KB Output is correct
48 Correct 270 ms 221228 KB Output is correct
49 Correct 270 ms 221300 KB Output is correct
50 Correct 268 ms 221296 KB Output is correct
51 Correct 265 ms 221320 KB Output is correct
52 Correct 78 ms 58692 KB Output is correct
53 Correct 289 ms 223744 KB Output is correct
54 Correct 269 ms 219276 KB Output is correct
55 Correct 263 ms 220456 KB Output is correct
56 Correct 2 ms 1620 KB Output is correct
57 Correct 257 ms 219240 KB Output is correct
58 Runtime error 864 ms 2097152 KB Execution killed with signal 9
59 Halted 0 ms 0 KB -