제출 #639828

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

fish

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

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

#define maxn 100005

int num[maxn];
vector<int> yval[maxn],impt[maxn];
map<int,ll> wpfx[maxn];
vector<ll> dp[3][maxn],dppfx[3][maxn],dpsfx[3][maxn];

ll max_weights(int N,int M,vi X,vi Y,vi W){
	for(int i=0;i<M;++i){
		++X[i],++Y[i];
		yval[X[i]].pb(Y[i]);
		wpfx[X[i]][Y[i]]=W[i];
		if(X[i]-1>=1)impt[X[i]-1].pb(Y[i]);
		if(X[i]+1<=N)impt[X[i]+1].pb(Y[i]);
	}
	impt[0].pb(0);
	for(int i=0;i<=N+1;++i){
		yval[i].pb(0);
		sort(all(yval[i]));
		for(int x=0;x<=2;++x){
			dp[x][i].resize(num[i]+5,0);
			dppfx[x][i].resize(num[i]+5,0);
			dpsfx[x][i].resize(num[i]+5,0);
		}
		disc(impt[i]);
		num[i]=impt[i].size();
		//pf("impt %d: ",i);
		//for(int x:impt[i]){
			//pf("%d ",x);
		//}
		//pf("\n");
		for(int j=1;j<num[i];++j){
			int ycur=yval[i][j],ypv=yval[i][j-1];
			wpfx[i][ycur]+=wpfx[i][ypv];
		}
	}
	for(int pos=N;pos>=1;--pos){
		//pf("%d\n",pos);
		for(int pvid=0;pvid<num[pos-1];++pvid){
			int pv=impt[pos-1][pvid];
			int low1=yval[pos-1][ub(yval[pos-1],pv)-1];
			int low=yval[pos][ub(yval[pos],pv)-1];
			
			int i=lb(impt[pos],pv);
			mxto(dp[0][pos][pvid],dpsfx[0][pos+1][i]-wpfx[pos-1][low1]);
			i=ub(impt[pos],pv)-1;
			mxto(dp[1][pos][pvid],dppfx[1][pos+1][i]+wpfx[pos][low]);
			mxto(dp[1][pos][pvid],dp[2][pos+1][pvid]+wpfx[pos][low]);
			mxto(dp[2][pos][pvid],dpsfx[0][pos+1][low]-wpfx[pos-1][low1]);
			mxto(dp[2][pos][pvid],dppfx[2][pos+1][low1]);
			if(pvid!=0)mxto(dp[0][pos][pvid],dp[1][pos][pvid]);
			
			//pf("dp %d %d(=%d): ",pos,pvid,pv);
			//for(int x=0;x<3;++x){
				//pf("%d ",dp[x][pos][pvid]);
			//}
			//pf("\n");
			
			if(pos==1)continue;
			int low2=yval[pos-2][ub(yval[pos-2],pv)-1];//lowest thing higher than pv
			dppfx[0][pos][pvid]=dpsfx[0][pos][pvid]=dp[0][pos][pvid]+wpfx[pos-2][low2];
			dppfx[1][pos][pvid]=dpsfx[1][pos][pvid]=dp[1][pos][pvid]+wpfx[pos-1][low1];
			dppfx[2][pos][pvid]=dpsfx[2][pos][pvid]=dp[2][pos][pvid];
		}
		for(int i=1;i<num[pos-1];++i){
			for(int x=0;x<3;++x){
				dppfx[x][pos][i]+=dppfx[x][pos][i-1];
			}
		}
		for(int i=num[pos-1]-2;i>=0;--i){
			for(int x=0;x<3;++x){
				dpsfx[x][pos][i]+=dpsfx[x][pos][i+1];
			}
		}
	}
	return dp[0][1][0];
}

• 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