Submission #826723

#	Time	Username	Problem	Language	Result	Execution time	Memory
826723		arnold518	Catfish Farm (IOI22_fish)	C++17	100 / 100	155 ms	39144 KiB

fish

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e18;

int N, M;
vector<pii> V[MAXN+10];
vector<ll> dp1[MAXN+10], dp2[MAXN+10];

struct BIT
{
	ll tree[MAXN+10];
	void init() { for(int i=1; i<=N; i++) tree[i]=-INF; }
	void update(int i, ll k) { for(; i<=N; i+=(i&-i)) tree[i]=max(tree[i], k); }
	ll query(int i) { ll ret=-INF; for(; i>0; i-=(i&-i)) ret=max(ret, tree[i]); return ret; }
}bit1, bit2;

ll max_weights(int _N, int _M, vector<int> _X, vector<int> _Y, vector<int> _W)
{
	N=_N; M=_M;
	for(int i=0; i<M; i++)
	{
		int x=_X[i]+1, y=_Y[i]+1, w=_W[i];
		V[x].push_back({y, w});
	}
	for(int i=0; i<=N+1; i++)
	{
		sort(V[i].begin(), V[i].end());
		if(V[i].empty() || V[i][0].first!=1) V[i].push_back({1, 0});
		if(V[i].back().first!=N) V[i].push_back({N, 0});
		sort(V[i].begin(), V[i].end());

		dp1[i]=vector<ll>(V[i].size(), -INF);
		dp2[i]=vector<ll>(V[i].size(), -INF);
	}

	
	bit1.init(); bit2.init();
	dp2[0][0]=0; dp1[0][dp1[0].size()-1]=0;
	ll p=-INF, q=-INF, ans=0;
	for(int i=0; i<=N+1; i++)
	{
		int t=V[i].size();
		if(i-1>=0) p=max(p, dp2[i-1][0]);
		if(i-2>=0) q=max(q, dp1[i-2].back());

		dp1[i][0]=max(dp1[i][0], p+V[i][0].second);
		if(i-2>=0) dp1[i][0]=max(dp1[i][0], dp1[i-2].back()+V[i][0].second);
		dp2[i][t-1]=max(dp2[i][t-1], q+V[i][t-1].second);
		for(int j=0; j<t; j++)
		{
			auto [y, w] = V[i][j];
			dp1[i][j]=max(dp1[i][j], bit1.query(y-1)+w);
			bit1.update(y, dp1[i][j]);
		}
		for(int j=t-1; j>=0; j--)
		{
			auto [y, w] = V[i][j];
			dp2[i][j]=max(dp2[i][j], bit2.query(N-y)+w);
			bit2.update(N-y+1, dp2[i][j]);
		}

		ans=max(ans, dp2[i][0]);
		// for(auto it : dp1[i]) printf("%lld ", it); printf("\n");
		// for(auto it : dp2[i]) printf("%lld ", it); printf("\n");
		// printf("\n");
	}
	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