oj.uz

Submission #640016

# Submission time Handle Problem Language Result Execution time Memory
640016 2022-09-13T09:24:47 Z jamezzz Catfish Farm (IOI22_fish) C++17
9 / 100
 541 ms 112568 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],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]);
						mxto(dp[1][pos][id],dpsfx[pos+2][i2+1]);
					}
				}
			}
			
			//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("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: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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 71004 KB Output is correct
2 Correct 171 ms 77440 KB Output is correct
3 Correct 81 ms 68760 KB Output is correct
4 Correct 80 ms 68728 KB Output is correct
5 Correct 350 ms 108012 KB Output is correct
6 Correct 541 ms 112568 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 253 ms 81684 KB Output is correct
3 Correct 286 ms 90564 KB Output is correct
4 Correct 154 ms 70988 KB Output is correct
5 Correct 177 ms 77400 KB Output is correct
6 Correct 11 ms 21452 KB Output is correct
7 Correct 10 ms 21456 KB Output is correct
8 Correct 10 ms 21356 KB Output is correct
9 Correct 11 ms 21332 KB Output is correct
10 Correct 83 ms 68780 KB Output is correct
11 Correct 83 ms 68776 KB Output is correct
12 Correct 172 ms 74768 KB Output is correct
13 Correct 201 ms 83332 KB Output is correct
14 Correct 166 ms 74076 KB Output is correct
15 Correct 208 ms 80212 KB Output is correct
16 Correct 169 ms 74136 KB Output is correct
17 Correct 183 ms 79848 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 68672 KB Output is correct
2 Correct 103 ms 68812 KB Output is correct
3 Incorrect 174 ms 65220 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21452 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 10 ms 21388 KB Output is correct
4 Correct 10 ms 21460 KB Output is correct
5 Correct 10 ms 21332 KB Output is correct
6 Correct 10 ms 21332 KB Output is correct
7 Correct 10 ms 21360 KB Output is correct
8 Correct 10 ms 21396 KB Output is correct
9 Incorrect 11 ms 21588 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '192851496371'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21452 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 10 ms 21388 KB Output is correct
4 Correct 10 ms 21460 KB Output is correct
5 Correct 10 ms 21332 KB Output is correct
6 Correct 10 ms 21332 KB Output is correct
7 Correct 10 ms 21360 KB Output is correct
8 Correct 10 ms 21396 KB Output is correct
9 Incorrect 11 ms 21588 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '192851496371'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21452 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 10 ms 21388 KB Output is correct
4 Correct 10 ms 21460 KB Output is correct
5 Correct 10 ms 21332 KB Output is correct
6 Correct 10 ms 21332 KB Output is correct
7 Correct 10 ms 21360 KB Output is correct
8 Correct 10 ms 21396 KB Output is correct
9 Incorrect 11 ms 21588 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '192851496371'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 68672 KB Output is correct
2 Correct 103 ms 68812 KB Output is correct
3 Incorrect 174 ms 65220 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 71004 KB Output is correct
2 Correct 171 ms 77440 KB Output is correct
3 Correct 81 ms 68760 KB Output is correct
4 Correct 80 ms 68728 KB Output is correct
5 Correct 350 ms 108012 KB Output is correct
6 Correct 541 ms 112568 KB Output is correct
7 Correct 10 ms 21332 KB Output is correct
8 Correct 253 ms 81684 KB Output is correct
9 Correct 286 ms 90564 KB Output is correct
10 Correct 154 ms 70988 KB Output is correct
11 Correct 177 ms 77400 KB Output is correct
12 Correct 11 ms 21452 KB Output is correct
13 Correct 10 ms 21456 KB Output is correct
14 Correct 10 ms 21356 KB Output is correct
15 Correct 11 ms 21332 KB Output is correct
16 Correct 83 ms 68780 KB Output is correct
17 Correct 83 ms 68776 KB Output is correct
18 Correct 172 ms 74768 KB Output is correct
19 Correct 201 ms 83332 KB Output is correct
20 Correct 166 ms 74076 KB Output is correct
21 Correct 208 ms 80212 KB Output is correct
22 Correct 169 ms 74136 KB Output is correct
23 Correct 183 ms 79848 KB Output is correct
24 Correct 82 ms 68672 KB Output is correct
25 Correct 103 ms 68812 KB Output is correct
26 Incorrect 174 ms 65220 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
27 Halted 0 ms 0 KB -