제출 #640017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640017		jamezzz	메기 농장 (IOI22_fish)	C++17	100 / 100	515 ms	110492 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];
vector<ii> ywpr[maxn];
vector<ll> wpfx[maxn];
vector<ll> dp[2][maxn],dppfx[maxn],dpsfx[maxn],dppfx2[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]);
		ywpr[X[i]].pb({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]);
	}
	for(int i=0;i<=N+1;++i){
		yval[i].pb(0);
		ywpr[i].pb({0,0});
		sort(all(yval[i]));
		sort(all(ywpr[i]));
		wpfx[i].resize(yval[i].size()+5,0);
		for(int j=1;j<yval[i].size();++j){
			wpfx[i][j]+=wpfx[i][j-1]+ywpr[i][j].se;
		}
		
		impt[i].pb(0);
		disc(impt[i]);
		num[i]=impt[i].size();
		for(int x=0;x<2;++x){
			dp[x][i].resize(num[i]+5,0);
			dppfx[i].resize(num[i]+5,0);
			dpsfx[i].resize(num[i]+5,0);
			dppfx2[i].resize(num[i]+5,0);
		}
	}
	for(int pos=N;pos>=0;--pos){
		for(int id=0;id<num[pos];++id){
			int h=impt[pos][id];
			dbg("%d\n",h);
			
			//transition strictly downwards
			{
				int i=lb(impt[pos+1],h)-1;
				int y=ub(yval[pos+1],h)-1;
				dbg("down i=%d y=%d\n",i,y);
				if(h!=0){
					mxto(dp[1][pos][id],dppfx[pos+1][i]+wpfx[pos+1][y]);
					if(pos<=N-2){
						int i2=ub(impt[pos+2],h)-1;
						int y2=ub(yval[pos+1],h)-1;
						dbg("i2=%d, y2=%d\n",i2,y2);
						mxto(dp[1][pos][id],dppfx2[pos+2][i2]+wpfx[pos+1][y2]);//x 0 y<=x
						mxto(dp[1][pos][id],dpsfx[pos+2][i2+1]);//x 0 y>x
					}
				}
			}
			
			//transition upwards
			{
				int i=lb(impt[pos+1],h);
				int y=ub(yval[pos],h)-1;
				dbg("up i=%d y=%d\n",i,y);
				if(i!=impt[pos+1].size()){
					mxto(dp[0][pos][id],dpsfx[pos+1][i]-wpfx[pos][y]);
				}
				if(h!=0){
					mxto(dp[0][pos][id],dp[1][pos][id]);
				}
			}
			
			dbg("dp[%d][%d][%d]: %d\n",0,pos,id,dp[0][pos][id]);
			dbg("dp[%d][%d][%d]: %d\n",1,pos,id,dp[1][pos][id]);
			dbg("\n");
			
			if(pos!=0){
				int i=ub(yval[pos],h)-1;
				if(id!=0)dppfx[pos][id]=dp[1][pos][id]-wpfx[pos][i];
				dppfx2[pos][id]=dp[0][pos][id];
				i=ub(yval[pos-1],h)-1;
				dpsfx[pos][id]=dp[0][pos][id]+wpfx[pos-1][i];
			}
		}
		for(int id=1;id<num[pos];++id){
			mxto(dppfx[pos][id],dppfx[pos][id-1]);
			mxto(dppfx2[pos][id],dppfx2[pos][id-1]);
		}
		for(int id=num[pos]-2;id>=0;--id){
			mxto(dpsfx[pos][id],dpsfx[pos][id+1]);
		}
		
		#ifdef DEBUG
		pf("dppfx[%d]: ",pos);
		for(int id=0;id<num[pos];++id)pf("%d ",dppfx[pos][id]);
		pf("\n");
		pf("dppfx2[%d]: ",pos);
		for(int id=0;id<num[pos];++id)pf("%d ",dppfx2[pos][id]);
		pf("\n");
		pf("dpsfx[%d]: ",pos);
		for(int id=0;id<num[pos];++id)pf("%d ",dpsfx[pos][id]);
		pf("\n\n");
		#endif
	}
	return dp[0][0][0];
}

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'll max_weights(int, int, vi, vi, vi)':
fish.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int j=1;j<yval[i].size();++j){
      |               ~^~~~~~~~~~~~~~~
fish.cpp:101:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     if(i!=impt[pos+1].size()){
      |        ~^~~~~~~~~~~~~~~~~~~~

• 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