oj.uz

Submission #659430

# Submission time Handle Problem Language Result Execution time Memory
659430 2022-11-17T17:27:04 Z pere_gil Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 2097152 KB 
#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
             
typedef long long ll;
#define all(x) x.begin(),x.end()

bool deb_inf_col=false;
bool deb_inf_state=false;

void pri(string s, vector<ll> v){
	printf("%s: ",s.c_str());
	for(ll i: v) printf("%lld ",i);
	printf("\n");
}

void pri(string s, vector<ll> a, vector<ll> b){
	printf("%s: ",s.c_str());
	for(ll i: a) printf("%lld ",b[i]);
	printf("\n");
}

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){

	vector<ll> sum[n],fish[n],temp_pier[n],pier[n];
	vector<pair<ll,ll>> inf_fish[n];
	for(int i=0;i<m;i++) inf_fish[x[i]].push_back({y[i]+1,w[i]});
	for(int i=0;i<n;i++){
		sum[i].push_back(0); fish[i].push_back(0); temp_pier[i].push_back(0);

		sort(all(inf_fish[i]));
		
		for(int j=0;j<(int)inf_fish[i].size();j++){
			fish[i].push_back(inf_fish[i][j].first);
			sum[i].push_back(inf_fish[i][j].second);
			if(i) temp_pier[i-1].push_back(inf_fish[i][j].first);
			if(i!=n-1) temp_pier[i+1].push_back(inf_fish[i][j].first);
		}
	}
	vector<ll> left[n],me[n],right[n];
	for(int i=0;i<n;i++){

		sort(all(temp_pier[i]));
		pier[i].push_back(temp_pier[i][0]);
		for(int j=1;j<(int)temp_pier[i].size();j++)
			if(temp_pier[i][j]!=temp_pier[i][j-1])
				pier[i].push_back(temp_pier[i][j]);
		
		left[i].assign(pier[i].size(),0);
		me[i].assign(pier[i].size(),0);
		right[i].assign(pier[i].size(),0);
		
		//sum:
		for(int j=1;j<(int)sum[i].size();j++)
			sum[i][j]+=sum[i][j-1];
		
		//left:
		if(i){
			for(int j=0,k=0;j<(int)pier[i].size();){
				if(k==(int)fish[i-1].size()-1){
					left[i][j]=k;
					j++;
				}
				else if(pier[i][j]>=fish[i-1][k] && pier[i][j]<fish[i-1][k+1]){
					left[i][j]=k;
					j++;
				}
				else k++;
			}
		}

		//me:
		for(int j=0,k=0;j<(int)pier[i].size();){
			if(k==(int)fish[i].size()-1){
				me[i][j]=k;
				j++;
			}
			else if(pier[i][j]>=fish[i][k] && pier[i][j]<fish[i][k+1]){
				me[i][j]=k;
				j++;
			}
			else k++;
		}

		//right:
		if(i!=n-1){
			for(int j=0,k=0;j<(int)pier[i].size();){
				if(k==(int)fish[i+1].size()-1){
					right[i][j]=k;
					j++;
				}
				else if(pier[i][j]>=fish[i+1][k] && pier[i][j]<fish[i+1][k+1]){
					me[i][j]=k;
					j++;
				}
				else k++;
			}
		}
	}

	if(deb_inf_col){
		for(int i=0;i<n;i++){
			printf("%d:\n",i);
			pri("fish:",fish[i]);
			pri("sum:",sum[i]);
			pri("pier:",pier[i]);
			if(i) pri("left:",left[i],fish[i-1]);
			pri("me:",me[i],fish[i]);
			if(i!=n-1) pri("right:",right[i],fish[i+1]);
			printf("\n");
		}
	}
	
	vector<vector<vector<ll>>> dp[n];
	for(int i=0;i<n;i++){
		int j=(i>=2) ? pier[i-2].size() : 1;
		int k=(i) ? pier[i-1].size() : 1;
		int l=pier[i].size();
		dp[i].assign(j,vector<vector<ll>>(k,vector<ll>(l,0)));
	}
	
	for(int i=1;i<n;i++){
		int size_j=(i>=2) ? pier[i-2].size() : 1;
		for(int j=0;j<size_j;j++){
			for(int k=0;k<(int)pier[i-1].size();k++){
				
				ll prev=0;
				int size_l=(i>=3) ? pier[i-3].size() : 1;
				int pos=0;
				for(int l=0;l<size_l;l++){
					ll aux=dp[i-1][l][j][k];
					if(aux>=prev){
						prev=aux;
						pos=l;
					}
				}
				
				for(int l=0;l<(int)pier[i].size();l++){
					dp[i][j][k][l]+=prev;

					if(deb_inf_state){
						if(i>=2) printf("%d: %lld\n",i-2,pier[i-2][j]);
						printf("%d: %lld\n",i-1,pier[i-1][k]);
						printf("%d: %lld\n",i,pier[i][l]);
						printf("prev: %lld at %d %d %d\n",prev,pos,j,k);
					}
					
					if(pier[i-1][k]>=pier[i][l]){
						ll up=sum[i][right[i-1][k]];
						ll down=sum[i][me[i][l]];

						if(deb_inf_state){
							printf("sum in %d\n",i);
							printf("up: %lld\n",fish[i][right[i-1][k]]);
							printf("down: %lld\n",fish[i][me[i][l]]);
							printf("-> %lld - %lld = %lld\n",up,down,up-down);
						}
						
						dp[i][j][k][l]+=sum[i][right[i-1][k]]-sum[i][me[i][l]];
					}
					else{
						if(deb_inf_state) printf("sum in %d\n",i-1);
						if(i>=2 && pier[i-2][j]>=pier[i-1][k]){
							ll up=sum[i-1][left[i][l]];
							ll down=sum[i-1][right[i-2][j]];

							if(deb_inf_state){
								printf("tallest in middle: %d\n",i-2);
								printf("up: %lld\n",fish[i-1][left[i][l]]);
								printf("down: %lld\n",fish[i-1][right[i-2][j]]);
								printf("-> %lld - %lld = %lld\n",up,down,up-down);
							}
							
							dp[i][j][k][l]+=sum[i-1][left[i][l]]-sum[i-1][right[i-2][j]];
						}
						else{
							ll up=sum[i-1][left[i][l]];
							ll down=sum[i-1][me[i-1][k]];
							
							if(deb_inf_state){
								printf("tallest in back: %d\n",i-1);
								printf("up: %lld\n",fish[i-1][left[i][l]]);
								printf("down: %lld\n",fish[i-1][me[i-1][k]]);
								printf("-> %lld - %lld = %lld\n",up,down,up-down);
							}
							
							dp[i][j][k][l]+=sum[i-1][left[i][l]]-sum[i-1][me[i-1][k]];
						}
					}
					if(deb_inf_state){
						printf("----> %lld\n",dp[i][j][k][l]);
						printf("\n");
					}
				}
			}
		}
	}
	
	ll res=0;
	int size_i=(n>=3) ? pier[n-3].size() : 1;
	for(int i=0;i<size_i;i++)
		for(int j=0;j<(int)pier[n-2].size();j++)
			for(int k=0;k<(int)pier[n-1].size();k++)
				res=max(res,dp[n-1][i][j][k]);
	
	return res;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 67428 KB Output is correct
2 Correct 152 ms 78996 KB Output is correct
3 Correct 82 ms 52724 KB Output is correct
4 Correct 80 ms 52684 KB Output is correct
5 Execution timed out 1142 ms 2014080 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 853 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 52664 KB Output is correct
2 Correct 89 ms 52604 KB Output is correct
3 Correct 149 ms 63824 KB Output is correct
4 Correct 127 ms 64232 KB Output is correct
5 Correct 236 ms 83224 KB Output is correct
6 Correct 203 ms 82728 KB Output is correct
7 Correct 200 ms 83276 KB Output is correct
8 Correct 199 ms 83272 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 224 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Incorrect 8 ms 3284 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '799098388912'
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 224 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Incorrect 8 ms 3284 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '799098388912'
11 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 224 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Incorrect 8 ms 3284 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '799098388912'
11 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 52664 KB Output is correct
2 Correct 89 ms 52604 KB Output is correct
3 Correct 149 ms 63824 KB Output is correct
4 Correct 127 ms 64232 KB Output is correct
5 Correct 236 ms 83224 KB Output is correct
6 Correct 203 ms 82728 KB Output is correct
7 Correct 200 ms 83276 KB Output is correct
8 Correct 199 ms 83272 KB Output is correct
9 Correct 307 ms 112744 KB Output is correct
10 Incorrect 185 ms 62764 KB 1st lines differ - on the 1st token, expected: '36454348383152', found: '36364983059693'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 67428 KB Output is correct
2 Correct 152 ms 78996 KB Output is correct
3 Correct 82 ms 52724 KB Output is correct
4 Correct 80 ms 52684 KB Output is correct
5 Execution timed out 1142 ms 2014080 KB Time limit exceeded
6 Halted 0 ms 0 KB -