Submission #745391

#	Time	Username	Problem	Language	Result	Execution time	Memory
745391		CSQ31	Catfish Farm (IOI22_fish)	C++17	100 / 100	284 ms	81228 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const ll INF = 1e18;
const int MAXN = 2e5+5;
vector<pii>fish[MAXN];
vector<ll>dp[2][MAXN],crd[MAXN],pref[MAXN];
void chmax(ll &x,ll y){
	x = max(x,y);
}
long long max_weights(int n, int m, vector<int> X, vector<int> Y,vector<int> W) {
	ll ans = 0;
	for(int i=0;i<m;i++)fish[X[i]].pb({Y[i],W[i]});
	for(int i=0;i<n;i++)sort(all(fish[i]));
	for(int i=0;i<n;i++){
		for(pii z:fish[i])crd[i].pb(z.fi);
		if(i)for(pii z:fish[i-1])crd[i].pb(z.fi);
		if(i+1<n)for(pii z:fish[i+1])crd[i].pb(z.fi);
		
		crd[i].pb(-1);
		sort(all(crd[i]));
		crd[i].resize(unique(all(crd[i])) - crd[i].begin());
		int s = sz(crd[i]);
		
		dp[0][i].assign(s,-INF);
		dp[1][i].assign(s,-INF);
		
		pref[i].assign(s,0);
		for(pii z:fish[i]){
			int p = lb(all(crd[i]),z.fi) - crd[i].begin();
			pref[i][p] = z.se;
		}
		for(int j=1;j<s;j++)pref[i][j]+=pref[i][j-1];
	}
	
	//initialize column one 
	for(ll &x:dp[0][0])x = 0;
	dp[1][0][sz(crd[0])-1] = 0;
	for(int i=1;i<n;i++){
		//last pier is lower
		ll mx = -INF;
		int ptr = -1;
		for(int j=0;j<sz(crd[i]);j++){
			while(ptr + 1 < sz(crd[i-1]) && crd[i-1][ptr+1] <= crd[i][j]){
				ptr++;
				chmax(mx,dp[0][i-1][ptr] - pref[i-1][ptr]);
			}
			chmax(dp[0][i][j],mx + pref[i-1][ptr]);
		}
		//;ast pier is higher
		mx = -INF;
		ptr = sz(crd[i-1]);
		ll sum = pref[i].back();
		vector<pii>f = fish[i];
		for(int j=sz(crd[i])-1;j>=0;j--){
			while(ptr - 1 >= 0 && crd[i-1][ptr-1] >= crd[i][j]){
				ptr--;
				while(!f.empty() && f.back().fi > crd[i-1][ptr]){
					sum-=f.back().se;
					f.pop_back();
				}
				chmax(mx,dp[1][i-1][ptr] + sum);
				chmax(mx,dp[0][i-1][ptr] + sum);
			}
			chmax(dp[1][i][j],mx - pref[i][j]);
		}
		if(i>=1){
			//i-1 column is empty :
			//i-2 pier is shorter
			sum = 0;
			mx = -INF;
			int ptr0 = -1; //column i-2
			int ptr1 = -1; //column i-1
			for(int j=0;j<sz(crd[i]);j++){
				while(ptr0 + 1 < sz(crd[i-2]) && crd[i-2][ptr0+1] <= crd[i][j]){
					ptr0++;
					mx = max(mx,dp[0][i-2][ptr0]);
					mx = max(mx,dp[1][i-2][ptr0]);
				}
				while(ptr1 + 1 < sz(fish[i-1]) && fish[i-1][ptr1+1].fi <= crd[i][j]){
					ptr1++;
					sum+=fish[i-1][ptr1].se;
				}
				chmax(dp[0][i][j],mx + sum);
			}
			//i-2 pier is higher
			f = fish[i-1];
			sum = pref[i-1].back();
			mx = -INF;
			ptr0 = sz(crd[i-2]);
			ptr1 = sz(f) - 1;
			for(int j=sz(crd[i])-1;j>=0;j--){
				while(ptr0 - 1 >= 0 && crd[i-2][ptr0-1] >= crd[i][j]){
					ptr0--;
					while(ptr1 >= 0 && f[ptr1].fi > crd[i-2][ptr0]){
						sum-=f[ptr1].se;
						ptr1--;
					}
					chmax(mx,dp[0][i-2][ptr0] + sum);
					chmax(mx,dp[1][i-2][ptr0] + sum);
				}

				chmax(dp[0][i][j],mx);
			}
		}
		/*
		cout<<"at "<<i<<'\n';
		for(int x:crd[i])cout<<x<<" ";cout<<'\n';
		for(ll x:dp[0][i])cout<<x<<" ";cout<<'\n';
		for(ll x:dp[1][i])cout<<x<<" ";cout<<'\n';
		* */
		
		
	}
	for(ll x:dp[0][n-1])ans = max(ans,x);
	for(ll x:dp[1][n-1])ans = max(ans,x);
	if(n>=2){
		int ptr = -1;
		ll sum = 0;
		for(int i=0;i<sz(crd[n-2]);i++){
			while(ptr + 1 < sz(fish[n-1]) && fish[n-1][ptr+1].fi <= crd[n-2][i]){
				ptr++;
				sum+=fish[n-1][ptr].se;
			}
			chmax(ans,dp[0][n-2][i]+sum);
			chmax(ans,dp[1][n-2][i]+sum);
		}
	}
	return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16