oj.uz

답안 #639841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
639841 2022-09-12T08:51:24 Z jamezzz 메기 농장 (IOI22_fish) C++17
0 / 100
 199 ms 160316 KB 
#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();
		#ifdef DEBUG
		pf("impt %d: ",i);
		for(int x:impt[i]){
			pf("%d ",x);
		}
		pf("\n");
		#endif 
		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];
			
			dbg("low1: %d, low: %d\n",low1,low);
			
			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]);
			i=lb(impt[pos],pv);
			mxto(dp[2][pos][pvid],dpsfx[0][pos+1][i]-wpfx[pos-1][low1]);
			i=ub(impt[pos],pv)-1;
			mxto(dp[2][pos][pvid],dppfx[2][pos+1][i]);
			if(pvid!=0)mxto(dp[0][pos][pvid],dp[1][pos][pvid]);
			
			#ifdef DEBUG
			pf("dp %d %d(=%d): ",pos,pvid,pv);
			for(int x=0;x<3;++x){
				pf("%d ",dp[x][pos][pvid]);
			}
			pf("\n");
			#endif
			
			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){
				mxto(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){
				mxto(dpsfx[x][pos][i],dpsfx[x][pos][i+1]);
			}
		}
	}
	return dp[0][1][0];
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 199 ms 160316 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 30840 KB 1st lines differ - on the 1st token, expected: '2', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 76620 KB 1st lines differ - on the 1st token, expected: '10082010', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 30740 KB 1st lines differ - on the 1st token, expected: '3', found: '50'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 30740 KB 1st lines differ - on the 1st token, expected: '3', found: '50'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 30740 KB 1st lines differ - on the 1st token, expected: '3', found: '50'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 76620 KB 1st lines differ - on the 1st token, expected: '10082010', found: '0'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 199 ms 160316 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -