제출 #1306369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306369		vtnoo	메기 농장 (IOI22_fish)	C++17	0 / 100	1113 ms	377380 KiB

fish

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
const ll INF=1e18;
set<ll>s[MAXN];
unordered_map<ll,ll>dp[MAXN][2];
unordered_map<ll,ll>a[MAXN],pref[MAXN],prefMax[MAXN],sufMax[MAXN];
void chmax(ll &a,ll b){
	a=max(a,b);
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
	fore(i,0,M){
		X[i]++;Y[i]++;
		a[X[i]][Y[i]]+=W[i];
		s[X[i]-1].insert(Y[i]);
		s[X[i]].insert(Y[i]);
		s[X[i]+1].insert(Y[i]);
	}
	fore(i,0,N+1){
		s[i].insert(0);
		s[i].insert(N);
		if(i){
			ll sum=0;
			for(auto x:s[i]){
				dp[i][0][x]=dp[i][1][x]=prefMax[i][x]=sufMax[i][x]-INF;
				sum+=a[i][x];
				pref[i][x]=sum;
			}	
		}
	}
	dp[0][1][0]=0;
	dp[0][0][0]=-INF;
	ll ans=-INF;
	fore(i,1,N+1){
		//~ cout<<"======================"<<endl;
		ll ndp=-INF;
		for(auto x:s[i-1]){
			chmax(ndp,dp[i-1][0][x]);
			chmax(ndp,dp[i-1][1][x]);
		}
		ll best=-INF;
		for(auto x:s[i]){
			if(x==0){
				dp[i][0][x]=dp[i][1][x]=ndp;
			}
			auto it=s[i-1].upper_bound(x);
			it--;
			ll y=*it;
			chmax(dp[i][1][x],pref[i-1][y]+prefMax[i-1][y]); //x >= y
			if(i>1)chmax(dp[i][0][x],sufMax[i][x]-pref[i][x]); // x <= y
			ans=max({ans,dp[i][1][x],dp[i][0][x]});
			//~ cout<<i<<" "<<ans<<" "<<x<<" "<<dp[i][0][x]<<" "<<dp[i][1][x]<<endl;
		}
		for(auto x:s[i]){
			chmax(prefMax[i][x],best);
			chmax(prefMax[i][x],dp[i][1][x]-pref[i][x]);
			chmax(best,prefMax[i][x]);
		}
		best=-INF;
		if(i<N){
			for(auto it=--s[i+1].end();;it--){
				ll x=*it;
				auto jt=s[i].lower_bound(x);
				jt--;
				ll y=*jt;
				ll ant=max(dp[i][0][y],dp[i][1][y]);
				chmax(sufMax[i+1][x],best);
				chmax(sufMax[i+1][x],ant+pref[i+1][x]);
				chmax(best,sufMax[i+1][x]);
				if(it==s[i+1].begin())break;
			}
		}
	}
	return ans;
}

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