Submission #1077233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077233		pcc	Catfish Farm (IOI22_fish)	C++17	100 / 100	879 ms	93328 KiB

fish

#include "fish.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fs first
#define sc second
#define tiii tuple<int,int,int>
#define tlll tuple<ll,ll,ll>

const ll inf = 1e18;
const int mxn = 1e5+10;
vector<pii> fish[mxn];
vector<pll> dp[mxn][2];
ll big = 0;

ll f(int idx,int s,int e){
	ll re = 0;
	for(auto &[pos,w]:fish[idx]){
		if(pos>s&&pos<=e)re += w;
	}
	return re;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
	for(int i = 0;i<M;i++){
		fish[X[i]].push_back(pii(Y[i],W[i]));
	}
	for(int i = 0;i<N;i++)fish[i].push_back(pii(N,0));
	for(int i = 0;i<N;i++)sort(fish[i].begin(),fish[i].end());

	{
		vector<pii> v;
		for(auto &[pos,w]:fish[0]){
			if(pos)v.push_back(pii(pos-1,-1));
		}
		for(auto &[pos,w]:fish[1]){
			v.push_back(pii(pos,w));
			v.push_back(pii(pos,-1));
		}
		sort(v.begin(),v.end());
		ll sum = 0;
		for(auto &[a,b]:v){
			if(b == -1)dp[0][0].push_back(pll(a,sum));
			else sum += b;
		}
		sort(dp[0][0].begin(),dp[0][0].end());
		dp[0][0].resize(unique(dp[0][0].begin(),dp[0][0].end())-dp[0][0].begin());
	}

	for(int i = 1;i<N;i++){
		ll ls = 0,ms = 0,rs = 0;
		vector<tlll> v;

		//cerr<<"CALC "<<i<<":"<<endl;

		for(auto &[pos,w]:fish[i]){
			if(pos)v.push_back(tlll(pos-1,0,-1));
			v.push_back(tlll(pos,-4,w));
		}
		for(auto &[pos,w]:fish[i-1]){
			v.push_back(tlll(pos,0,-1));
			v.push_back(tlll(pos,-3,w));
		}
		for(auto &[pos,w]:fish[i+1]){
			v.push_back(tlll(pos,0,-1));
			v.push_back(tlll(pos,-5,w));
		}
		sort(v.begin(),v.end());v.resize(unique(v.begin(),v.end())-v.begin());
		for(auto &[pos,w]:dp[i-1][0])v.push_back(tlll(pos,-2,w));//tp == -2:trans
		if(i-2>=0){
			for(int j = 0;j<2;j++)for(auto &[pos,w]:dp[i-2][j])v.push_back(tlll(pos,-1,w));
		}
		sort(v.begin(),v.end());
		ll mx1 = -inf,mx2 = -inf;
		for(auto &[pos,tp,val]:v){
			//cerr<<"["<<pos<<','<<tp<<','<<val<<','<<ls<<' '<<ms<<' '<<rs<<"]"<<endl;
			if(tp == -5)rs+=val;
			else if(tp == -4)ms+=val;
			else if(tp == -3)ls+=val;
			else if(tp == -2)mx1 = max(mx1,val-ms-ls);
			else if(tp == -1)mx2 = max(mx2,val-ls);
			else{
				val = max({big+ls+rs,mx1+ls+rs,mx2+ls+rs});
			}
		}
		//cerr<<endl;
		mx1 = 0;
		reverse(v.begin(),v.end());
		for(auto &[pos,tp,val]:v){
			if(tp == -5)rs -= val;
			else if(tp == -1){
				mx1 = max(mx1,val);
			}
			else if(tp == 0){
				val = max(val,rs+mx1);
				dp[i][0].push_back(pll(pos,val));
			}
		}

		ls = rs = ms;
		mx1 = mx2 = -inf;
		v.clear();

		for(auto &[pos,w]:fish[i]){
			if(pos)v.push_back(tlll(pos-1,0,-1));
			ms += w;
			v.push_back(tlll(pos,-4,w));
		}
		for(auto &[pos,w]:fish[i-1]){
			ls += w;
			v.push_back(tlll(pos,0,-1));
			v.push_back(tlll(pos,-3,w));
		}
		for(auto &[pos,w]:fish[i+1]){
			rs += w;
			v.push_back(tlll(pos,0,-1));
			v.push_back(tlll(pos,-5,w));
		}
		sort(v.begin(),v.end());v.resize(unique(v.begin(),v.end())-v.begin());
		for(auto &[pos,w]:dp[i-1][0])v.push_back(tlll(pos,2,w));//tp == 2:trans
		for(auto &[pos,w]:dp[i-1][1])v.push_back(tlll(pos,2,w));//tp == 2:trans
		sort(v.rbegin(),v.rend());
		mx1 = -inf,mx2 = -inf;
		for(auto &[pos,tp,val]:v){
			if(tp == -5)rs-=val;
			else if(tp == -4)ms-=val;
			else if(tp == -3)ls-=val;
			else if(tp == 2)mx1 = max(mx1,val);
			else{
				val = mx1-ms+rs;
				dp[i][1].push_back(pll(pos,val));
			}
		}

		if(i-2>=0){
			for(int j = 0;j<2;j++)for(auto &[a,b]:dp[i-2][j])big = max(big,b);
		}

	}
	ll ans = 0;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<2;j++){
			for(auto [a,b]:dp[i][j])ans = max(ans,b);
			//cerr<<i<<' '<<j<<":";for(auto [a,b]:dp[i][j])cerr<<a<<','<<b<<' ';cerr<<endl;
		}
	}
	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