Submission #630561

#	Time	Username	Problem	Language	Result	Execution time	Memory
630561		CSQ31	Catfish Farm (IOI22_fish)	C++17	9 / 100	1093 ms	56800 KiB

fish

#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++){
		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]);
		}
		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);
			}
			
		}*/
		if(i<2)continue;
		for(int j=0;j<cnt[i];j++){
			for(int k=0;k<cnt[i-2];k++){
				if(st[i-2][k] <= st[i][j]){
					mx = max(dp[0][i-2][k],dp[1][i-2][k]);
					dp[0][i][j] = max(dp[0][i][j],mx+pre[0][i][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
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16