oj.uz

Submission #630538

# Submission time Handle Problem Language Result Execution time Memory
630538 2022-08-16T13:35:38 Z CSQ31 Catfish Farm (IOI22_fish) C++17
6 / 100
 310 ms 87328 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);
		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];
			}
			
			
		}*/
	}
  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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 49268 KB Output is correct
2 Correct 139 ms 54164 KB Output is correct
3 Correct 46 ms 37732 KB Output is correct
4 Correct 44 ms 37648 KB Output is correct
5 Incorrect 310 ms 87328 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18516 KB Output is correct
2 Correct 190 ms 56732 KB Output is correct
3 Correct 225 ms 62488 KB Output is correct
4 Correct 135 ms 50424 KB Output is correct
5 Correct 138 ms 55548 KB Output is correct
6 Correct 10 ms 18516 KB Output is correct
7 Correct 10 ms 18516 KB Output is correct
8 Correct 10 ms 18516 KB Output is correct
9 Correct 10 ms 18536 KB Output is correct
10 Correct 44 ms 37688 KB Output is correct
11 Correct 43 ms 37656 KB Output is correct
12 Correct 121 ms 50504 KB Output is correct
13 Correct 137 ms 55624 KB Output is correct
14 Correct 117 ms 50304 KB Output is correct
15 Correct 127 ms 50488 KB Output is correct
16 Correct 119 ms 50308 KB Output is correct
17 Correct 126 ms 53564 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 37736 KB Output is correct
2 Correct 46 ms 37616 KB Output is correct
3 Incorrect 86 ms 39368 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '1999703533'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18560 KB Output is correct
2 Correct 11 ms 18584 KB Output is correct
3 Correct 10 ms 18520 KB Output is correct
4 Correct 10 ms 18520 KB Output is correct
5 Correct 10 ms 18464 KB Output is correct
6 Correct 10 ms 18548 KB Output is correct
7 Correct 10 ms 18476 KB Output is correct
8 Correct 10 ms 18468 KB Output is correct
9 Incorrect 10 ms 18516 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18560 KB Output is correct
2 Correct 11 ms 18584 KB Output is correct
3 Correct 10 ms 18520 KB Output is correct
4 Correct 10 ms 18520 KB Output is correct
5 Correct 10 ms 18464 KB Output is correct
6 Correct 10 ms 18548 KB Output is correct
7 Correct 10 ms 18476 KB Output is correct
8 Correct 10 ms 18468 KB Output is correct
9 Incorrect 10 ms 18516 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18560 KB Output is correct
2 Correct 11 ms 18584 KB Output is correct
3 Correct 10 ms 18520 KB Output is correct
4 Correct 10 ms 18520 KB Output is correct
5 Correct 10 ms 18464 KB Output is correct
6 Correct 10 ms 18548 KB Output is correct
7 Correct 10 ms 18476 KB Output is correct
8 Correct 10 ms 18468 KB Output is correct
9 Incorrect 10 ms 18516 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 37736 KB Output is correct
2 Correct 46 ms 37616 KB Output is correct
3 Incorrect 86 ms 39368 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '1999703533'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 49268 KB Output is correct
2 Correct 139 ms 54164 KB Output is correct
3 Correct 46 ms 37732 KB Output is correct
4 Correct 44 ms 37648 KB Output is correct
5 Incorrect 310 ms 87328 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -