oj.uz

Submission #630548

# Submission time Handle Problem Language Result Execution time Memory
630548 2022-08-16T13:51:04 Z CSQ31 Catfish Farm (IOI22_fish) C++17
18 / 100
 406 ms 87400 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define sz(a) (int)(a.size())
//0 -> previous is lower
//1 -> previous is higher
const int MAXN = 111111;
vector<int>st[MAXN];
vector<pii>fish[MAXN];
vector<ll>dp[2][MAXN],pre[3][MAXN];
int cnt[MAXN];
const ll INF = -1e17;
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]++;
		fish[X[i]].push_back({Y[i],i});
	}
	for(int i=0;i<=n;i++){
		vector<pii>f;
		st[i].push_back(0);
		if(i){
			for(auto x:fish[i-1]){
				st[i].push_back(x.fi);
				f.push_back(x);
			}
		}
		for(auto x:fish[i]){
			st[i].push_back(x.fi);
			f.push_back(x);
		}
		for(auto x:fish[i+1]){
			st[i].push_back(x.fi);
			f.push_back(x);
		}
		sort(st[i].begin(),st[i].end());
		sort(f.begin(),f.end());
		st[i].resize(unique(st[i].begin(),st[i].end()) - st[i].begin());
		cnt[i] = st[i].size();
		for(int k=0;k<3;k++)pre[k][i].assign(cnt[i],0);
		for(int k=0;k<2;k++)dp[k][i].assign(cnt[i],INF);
		int ptr = -1;
		for(int j=0;j<cnt[i];j++){
			while(ptr+1 < sz(f) && f[ptr+1].fi <= st[i][j]){
				ptr++;
				int id = f[ptr].se;
				if(X[id] == i-1)pre[0][i][j]+=W[id];
				if(X[id] == i  )pre[1][i][j]+=W[id];
				if(X[id] == i+1)pre[2][i][j]+=W[id];
			}
		}
		for(int k=0;k<3;k++){
			for(int j=1;j<cnt[i];j++)pre[k][i][j]+=pre[k][i][j-1];
		}
	}
	dp[0][0][0] = 0;
	for(int i=1;i<=n;i++){
		/*
		for(int j=0;j<=n;j++){
			sum+=f[i-1][j];
			mx = max(mx,dp[0][i-1][j] - sum);
			dp[0][i][j] = max(dp[0][i][j],mx+sum);
		}*/
		ll mx = INF;
		int ptr = -1;
		for(int j=0;j<cnt[i];j++){
			while(ptr+1<cnt[i-1] && st[i-1][ptr+1] <= st[i][j]){
				ptr++;
				mx = max(mx,dp[0][i-1][ptr] - pre[1][i-1][ptr]);
			}
			dp[0][i][j] = max(dp[0][i][j],mx + pre[0][i][j]);
		}
		/*
		ll mx = INF;
		sum = 0;
		for(int j=0;j<=n;j++)sum+=f[i][j];
		for(int j=n;j>=0;j--){
			mx = max(dp[0][i-1][j]+sum,mx);
			mx = max(dp[1][i-1][j]+sum,mx);
			dp[1][i][j] = max(dp[1][i][j],mx - sum);
			sum-=f[i][j];
		}*/
		mx = INF;
		ptr = cnt[i-1];
		for(int j=cnt[i]-1;j>=0;j--){
			while(ptr-1>=0 && st[i-1][ptr-1] >= st[i][j]){
				ptr--;
				mx = max(mx,dp[0][i-1][ptr] + pre[2][i-1][ptr]);
				mx = max(mx,dp[1][i-1][ptr] + pre[2][i-1][ptr]);
			}
			dp[1][i][j] = max(dp[1][i][j],mx - pre[1][i][j]);	
		}
		/*
		if(i>=2){
			sum = 0;
			mx = INF;
			for(int j=0;j<=n;j++){
				sum+=f[i-1][j];
				mx = max(mx,dp[0][i-2][j]);
				mx = max(mx,dp[1][i-2][j]);
				dp[0][i][j] = max(dp[0][i][j],mx+sum);
			}
			mx = INF;
			for(int j=n;j>=0;j--){
				mx = max(mx,dp[0][i-2][j]+sum);
				mx = max(mx,dp[1][i-2][j]+sum);
				dp[0][i][j] = max(dp[0][i][j],mx-sum);
				sum-=f[i-1][j];
			}
			
			
		}*/
		if(i<2)continue;
		mx = INF;
		ptr = -1;
		for(int j=0;j<cnt[i];j++){
			while(ptr+1 < cnt[i-2] && st[i-2][ptr+1] <= st[i][j]){
				ptr++;
				mx = max(mx,dp[0][i-2][ptr]);
				mx = max(mx,dp[1][i-2][ptr]);
			}
			dp[0][i][j] = max(dp[0][i][j],mx + pre[0][i][j]);
		}
		mx = INF;
		ptr = cnt[i-2]-1;
		for(int j=cnt[i]-1;j>=0;j--){
			while(ptr-1>=0 && st[i-2][ptr-1] >= st[i][j]){
				ptr--;
				mx = max(mx,dp[0][i-2][ptr]+pre[2][i-2][ptr]);
				mx = max(mx,dp[1][i-2][ptr]+pre[2][i-2][ptr]);
			}
			dp[0][i][j] = max(dp[0][i][j],mx);
		}
	}
  ll ans = 0;
  for(ll x:dp[0][n])ans = max(ans,x);
  for(ll x:dp[1][n])ans = max(ans,x);
  return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 49380 KB Output is correct
2 Correct 163 ms 54136 KB Output is correct
3 Correct 47 ms 37636 KB Output is correct
4 Correct 54 ms 37732 KB Output is correct
5 Correct 406 ms 87400 KB Output is correct
6 Correct 384 ms 81868 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18516 KB Output is correct
2 Correct 189 ms 56744 KB Output is correct
3 Correct 220 ms 62492 KB Output is correct
4 Correct 115 ms 49328 KB Output is correct
5 Correct 139 ms 54172 KB Output is correct
6 Correct 12 ms 18512 KB Output is correct
7 Correct 13 ms 18516 KB Output is correct
8 Correct 10 ms 18516 KB Output is correct
9 Correct 11 ms 18572 KB Output is correct
10 Correct 57 ms 37628 KB Output is correct
11 Correct 49 ms 37712 KB Output is correct
12 Correct 117 ms 49344 KB Output is correct
13 Correct 140 ms 54068 KB Output is correct
14 Correct 130 ms 49056 KB Output is correct
15 Correct 129 ms 49240 KB Output is correct
16 Correct 114 ms 49156 KB Output is correct
17 Correct 133 ms 52232 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 37808 KB Output is correct
2 Correct 46 ms 37684 KB Output is correct
3 Correct 77 ms 38672 KB Output is correct
4 Correct 70 ms 39632 KB Output is correct
5 Correct 113 ms 43236 KB Output is correct
6 Correct 109 ms 43212 KB Output is correct
7 Correct 111 ms 43160 KB Output is correct
8 Correct 109 ms 43180 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18472 KB Output is correct
2 Correct 10 ms 18516 KB Output is correct
3 Correct 10 ms 18516 KB Output is correct
4 Correct 11 ms 18524 KB Output is correct
5 Correct 10 ms 18576 KB Output is correct
6 Correct 12 ms 18552 KB Output is correct
7 Correct 10 ms 18516 KB Output is correct
8 Correct 11 ms 18516 KB Output is correct
9 Correct 10 ms 18556 KB Output is correct
10 Correct 13 ms 18772 KB Output is correct
11 Incorrect 12 ms 18644 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18472 KB Output is correct
2 Correct 10 ms 18516 KB Output is correct
3 Correct 10 ms 18516 KB Output is correct
4 Correct 11 ms 18524 KB Output is correct
5 Correct 10 ms 18576 KB Output is correct
6 Correct 12 ms 18552 KB Output is correct
7 Correct 10 ms 18516 KB Output is correct
8 Correct 11 ms 18516 KB Output is correct
9 Correct 10 ms 18556 KB Output is correct
10 Correct 13 ms 18772 KB Output is correct
11 Incorrect 12 ms 18644 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18472 KB Output is correct
2 Correct 10 ms 18516 KB Output is correct
3 Correct 10 ms 18516 KB Output is correct
4 Correct 11 ms 18524 KB Output is correct
5 Correct 10 ms 18576 KB Output is correct
6 Correct 12 ms 18552 KB Output is correct
7 Correct 10 ms 18516 KB Output is correct
8 Correct 11 ms 18516 KB Output is correct
9 Correct 10 ms 18556 KB Output is correct
10 Correct 13 ms 18772 KB Output is correct
11 Incorrect 12 ms 18644 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 37808 KB Output is correct
2 Correct 46 ms 37684 KB Output is correct
3 Correct 77 ms 38672 KB Output is correct
4 Correct 70 ms 39632 KB Output is correct
5 Correct 113 ms 43236 KB Output is correct
6 Correct 109 ms 43212 KB Output is correct
7 Correct 111 ms 43160 KB Output is correct
8 Correct 109 ms 43180 KB Output is correct
9 Correct 113 ms 50952 KB Output is correct
10 Correct 95 ms 32856 KB Output is correct
11 Correct 183 ms 47060 KB Output is correct
12 Correct 10 ms 18520 KB Output is correct
13 Correct 10 ms 18580 KB Output is correct
14 Correct 10 ms 18520 KB Output is correct
15 Correct 12 ms 18520 KB Output is correct
16 Correct 10 ms 18516 KB Output is correct
17 Correct 11 ms 18516 KB Output is correct
18 Correct 43 ms 37616 KB Output is correct
19 Correct 57 ms 37740 KB Output is correct
20 Correct 56 ms 37628 KB Output is correct
21 Correct 49 ms 37640 KB Output is correct
22 Incorrect 156 ms 48804 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45419465258745'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 49380 KB Output is correct
2 Correct 163 ms 54136 KB Output is correct
3 Correct 47 ms 37636 KB Output is correct
4 Correct 54 ms 37732 KB Output is correct
5 Correct 406 ms 87400 KB Output is correct
6 Correct 384 ms 81868 KB Output is correct
7 Correct 10 ms 18516 KB Output is correct
8 Correct 189 ms 56744 KB Output is correct
9 Correct 220 ms 62492 KB Output is correct
10 Correct 115 ms 49328 KB Output is correct
11 Correct 139 ms 54172 KB Output is correct
12 Correct 12 ms 18512 KB Output is correct
13 Correct 13 ms 18516 KB Output is correct
14 Correct 10 ms 18516 KB Output is correct
15 Correct 11 ms 18572 KB Output is correct
16 Correct 57 ms 37628 KB Output is correct
17 Correct 49 ms 37712 KB Output is correct
18 Correct 117 ms 49344 KB Output is correct
19 Correct 140 ms 54068 KB Output is correct
20 Correct 130 ms 49056 KB Output is correct
21 Correct 129 ms 49240 KB Output is correct
22 Correct 114 ms 49156 KB Output is correct
23 Correct 133 ms 52232 KB Output is correct
24 Correct 55 ms 37808 KB Output is correct
25 Correct 46 ms 37684 KB Output is correct
26 Correct 77 ms 38672 KB Output is correct
27 Correct 70 ms 39632 KB Output is correct
28 Correct 113 ms 43236 KB Output is correct
29 Correct 109 ms 43212 KB Output is correct
30 Correct 111 ms 43160 KB Output is correct
31 Correct 109 ms 43180 KB Output is correct
32 Correct 10 ms 18472 KB Output is correct
33 Correct 10 ms 18516 KB Output is correct
34 Correct 10 ms 18516 KB Output is correct
35 Correct 11 ms 18524 KB Output is correct
36 Correct 10 ms 18576 KB Output is correct
37 Correct 12 ms 18552 KB Output is correct
38 Correct 10 ms 18516 KB Output is correct
39 Correct 11 ms 18516 KB Output is correct
40 Correct 10 ms 18556 KB Output is correct
41 Correct 13 ms 18772 KB Output is correct
42 Incorrect 12 ms 18644 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
43 Halted 0 ms 0 KB -