oj.uz

답안 #640014

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640014 2022-09-13T09:11:30 Z jamezzz 메기 농장 (IOI22_fish) C++17
0 / 100
 347 ms 111940 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];
vector<ii> ywpr[maxn];
vector<ll> wpfx[maxn];
vector<ll> dp[2][maxn],dppfx[maxn],dpsfx[maxn],dpsfx2[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+1)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);
			dpsfx2[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("%d %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;
						mxto(dp[1][pos][id],dppfx[pos+2][i2]+wpfx[pos+1][y2]);
						mxto(dp[1][pos][id],dpsfx2[pos+2][i2+1]+wpfx[pos][y]);
					}
				}
			}
			
			//transition upwards
			{
				int i=lb(impt[pos+1],h);
				int y=ub(yval[pos],h)-1;
				dbg("%d %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];
				i=ub(yval[pos-1],h)-1;
				dpsfx[pos][id]=dp[0][pos][id]+wpfx[pos-1][i];
				dpsfx2[pos][id]=dp[0][pos][id];
			}
		}
		for(int id=1;id<num[pos];++id){
			mxto(dppfx[pos][id],dppfx[pos][id-1]);
		}
		for(int id=num[pos]-2;id>=0;--id){
			mxto(dpsfx[pos][id],dpsfx[pos][id+1]);
			mxto(dpsfx2[pos][id],dpsfx2[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("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];
}

Compilation message

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:100:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     if(i!=impt[pos+1].size()){
      |        ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 71232 KB Output is correct
2 Correct 171 ms 78460 KB Output is correct
3 Correct 104 ms 68680 KB Output is correct
4 Correct 92 ms 68772 KB Output is correct
5 Incorrect 347 ms 111940 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 267 ms 81800 KB Output is correct
3 Correct 289 ms 92408 KB Output is correct
4 Correct 152 ms 71540 KB Output is correct
5 Correct 204 ms 78180 KB Output is correct
6 Correct 14 ms 21504 KB Output is correct
7 Correct 11 ms 21456 KB Output is correct
8 Correct 10 ms 21460 KB Output is correct
9 Correct 11 ms 21332 KB Output is correct
10 Correct 81 ms 68748 KB Output is correct
11 Correct 81 ms 68744 KB Output is correct
12 Incorrect 174 ms 75296 KB 1st lines differ - on the 1st token, expected: '40374264367003', found: '386547056729999'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 68788 KB Output is correct
2 Correct 84 ms 68656 KB Output is correct
3 Incorrect 133 ms 65312 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '22621104631'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21332 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 11 ms 21420 KB Output is correct
4 Correct 11 ms 21432 KB Output is correct
5 Correct 11 ms 21456 KB Output is correct
6 Correct 15 ms 21360 KB Output is correct
7 Correct 11 ms 21436 KB Output is correct
8 Correct 11 ms 21460 KB Output is correct
9 Incorrect 13 ms 21560 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '133337947195'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21332 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 11 ms 21420 KB Output is correct
4 Correct 11 ms 21432 KB Output is correct
5 Correct 11 ms 21456 KB Output is correct
6 Correct 15 ms 21360 KB Output is correct
7 Correct 11 ms 21436 KB Output is correct
8 Correct 11 ms 21460 KB Output is correct
9 Incorrect 13 ms 21560 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '133337947195'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 21332 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 11 ms 21420 KB Output is correct
4 Correct 11 ms 21432 KB Output is correct
5 Correct 11 ms 21456 KB Output is correct
6 Correct 15 ms 21360 KB Output is correct
7 Correct 11 ms 21436 KB Output is correct
8 Correct 11 ms 21460 KB Output is correct
9 Incorrect 13 ms 21560 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '133337947195'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 68788 KB Output is correct
2 Correct 84 ms 68656 KB Output is correct
3 Incorrect 133 ms 65312 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '22621104631'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 71232 KB Output is correct
2 Correct 171 ms 78460 KB Output is correct
3 Correct 104 ms 68680 KB Output is correct
4 Correct 92 ms 68772 KB Output is correct
5 Incorrect 347 ms 111940 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -