oj.uz

Submission #639992

# Submission time Handle Problem Language Result Execution time Memory
639992 2022-09-13T06:23:47 Z jamezzz Catfish Farm (IOI22_fish) C++17
0 / 100
 374 ms 109100 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+2],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

# Verdict Execution time Memory Grader output
1 Correct 155 ms 71048 KB Output is correct
2 Correct 182 ms 77924 KB Output is correct
3 Correct 103 ms 68684 KB Output is correct
4 Correct 98 ms 68824 KB Output is correct
5 Incorrect 374 ms 109100 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 289 ms 82556 KB Output is correct
3 Correct 306 ms 91972 KB Output is correct
4 Correct 155 ms 71552 KB Output is correct
5 Correct 185 ms 77956 KB Output is correct
6 Correct 12 ms 21424 KB Output is correct
7 Correct 12 ms 21408 KB Output is correct
8 Correct 12 ms 21452 KB Output is correct
9 Correct 13 ms 21460 KB Output is correct
10 Correct 86 ms 68792 KB Output is correct
11 Correct 84 ms 68780 KB Output is correct
12 Incorrect 173 ms 75300 KB 1st lines differ - on the 1st token, expected: '40374264367003', found: '386547056729999'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 68784 KB Output is correct
2 Correct 85 ms 68712 KB Output is correct
3 Incorrect 142 ms 65488 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 21332 KB Output is correct
2 Correct 11 ms 21416 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Correct 11 ms 21388 KB Output is correct
5 Correct 10 ms 21456 KB Output is correct
6 Correct 11 ms 21388 KB Output is correct
7 Correct 11 ms 21376 KB Output is correct
8 Correct 13 ms 21348 KB Output is correct
9 Incorrect 14 ms 21600 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '133337947195'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 11 ms 21416 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Correct 11 ms 21388 KB Output is correct
5 Correct 10 ms 21456 KB Output is correct
6 Correct 11 ms 21388 KB Output is correct
7 Correct 11 ms 21376 KB Output is correct
8 Correct 13 ms 21348 KB Output is correct
9 Incorrect 14 ms 21600 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '133337947195'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 11 ms 21416 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Correct 11 ms 21388 KB Output is correct
5 Correct 10 ms 21456 KB Output is correct
6 Correct 11 ms 21388 KB Output is correct
7 Correct 11 ms 21376 KB Output is correct
8 Correct 13 ms 21348 KB Output is correct
9 Incorrect 14 ms 21600 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '133337947195'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 68784 KB Output is correct
2 Correct 85 ms 68712 KB Output is correct
3 Incorrect 142 ms 65488 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 Correct 155 ms 71048 KB Output is correct
2 Correct 182 ms 77924 KB Output is correct
3 Correct 103 ms 68684 KB Output is correct
4 Correct 98 ms 68824 KB Output is correct
5 Incorrect 374 ms 109100 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -