oj.uz

Submission #639987

# Submission time Handle Problem Language Result Execution time Memory
639987 2022-09-13T06:14:35 Z jamezzz Catfish Farm (IOI22_fish) C++17
0 / 100
 232 ms 70604 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<int> wpfx[maxn];
vector<ll> dp[2][maxn],dppfx[maxn],dpsfx[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);
		}
	}
	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 i=ub(impt[pos+2],h)-1;
						int y=ub(yval[pos+2],h)-1;
						mxto(dp[1][pos][id],dppfx[pos+2][i]+wpfx[pos+1][y]);
						mxto(dp[1][pos][id],dpsfx[pos+2][i+1]-wpfx[pos+1][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];
			}
		}
		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]);
		}
		
		#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:99:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     if(i!=impt[pos+1].size()){
      |        ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 60368 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '2147442400'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19108 KB Output is correct
2 Incorrect 232 ms 70604 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '8579116350'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 57040 KB Output is correct
2 Correct 76 ms 57008 KB Output is correct
3 Incorrect 125 ms 55956 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '18158958703'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19100 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 11 ms 19104 KB Output is correct
5 Correct 12 ms 19028 KB Output is correct
6 Correct 11 ms 19092 KB Output is correct
7 Correct 10 ms 19004 KB Output is correct
8 Correct 10 ms 19004 KB Output is correct
9 Incorrect 12 ms 19156 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '141603623559'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19100 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 11 ms 19104 KB Output is correct
5 Correct 12 ms 19028 KB Output is correct
6 Correct 11 ms 19092 KB Output is correct
7 Correct 10 ms 19004 KB Output is correct
8 Correct 10 ms 19004 KB Output is correct
9 Incorrect 12 ms 19156 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '141603623559'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19100 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 11 ms 19104 KB Output is correct
5 Correct 12 ms 19028 KB Output is correct
6 Correct 11 ms 19092 KB Output is correct
7 Correct 10 ms 19004 KB Output is correct
8 Correct 10 ms 19004 KB Output is correct
9 Incorrect 12 ms 19156 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '141603623559'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 57040 KB Output is correct
2 Correct 76 ms 57008 KB Output is correct
3 Incorrect 125 ms 55956 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '18158958703'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 60368 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '2147442400'
2 Halted 0 ms 0 KB -