oj.uz

Submission #659485

# Submission time Handle Problem Language Result Execution time Memory
659485 2022-11-17T22:32:23 Z pere_gil Catfish Farm (IOI22_fish) C++17
12 / 100
 822 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_state=false;

void fill(vector<ll> &pier, vector<ll> &fish, vector<ll> &v){
	for(int i=0,j=0;i<(int)pier.size();)
		if(j==(int)fish.size()-1 || (pier[i]>=fish[j] && pier[i]<fish[j+1])){
			v[i]=j;
			i++;
		}
		else j++;
}

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);
		}
	}
	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]);

		for(int j=1;j<(int)fish[i].size();j++)
			sum[i][j]+=sum[i][j-1];
	}
	vector<ll> left[n],me[n],right[n];
	for(int i=0;i<n;i++){
		left[i].assign(pier[i].size(),0);
		me[i].assign(pier[i].size(),0);
		right[i].assign(pier[i].size(),0);

		if(i) fill(pier[i],fish[i-1],left[i]);
		fill(pier[i],fish[i],me[i]);
		if(i!=n-1) fill(pier[i],fish[i+1],right[i]);
	}
	
	vector<vector<ll>> dec[n],inc[n];
	for(int i=0;i<n;i++){
		int j=(i) ? pier[i-1].size() : 1;
		int k=pier[i].size();
		dec[i].assign(j,vector<ll>(k,0));
		inc[i].assign(j,vector<ll>(k,0));
	}

	for(int i=0;i<(int)pier[0].size();i++)
		for(int j=0;j<(int)pier[1].size();j++){
			ll aux=0;
			if(pier[0][i]>=pier[1][j])
				aux+=sum[1][right[0][i]]-sum[1][me[1][i]];
			else
				aux+=sum[0][left[1][j]]-sum[0][me[0][i]];
			dec[1][i][j]=inc[1][i][j]=aux;
		}

	for(int i=2;i<n;i++){
		for(int j=0;j<(int)pier[i-1].size();j++){

			//decreasing:
			if(pier[i-1][j]){
				ll prev=0;
				int pos=0;
				for(int k=0;k<(int)pier[i-2].size();k++){
					if(pier[i-2][k]<pier[i-1][j]) continue;
					ll aux=max(dec[i-1][k][j],inc[i-1][k][j]);
					if(aux>=prev){
						prev=aux;
						pos=k;
					}
				}
				for(int k=0;k<(int)pier[i].size();k++){
					if(pier[i][k]>pier[i-1][j]) break;

					if(deb_inf_state){
						ll up=sum[i][right[i-1][j]];
						ll down=sum[i][me[i][k]];
						printf("decreasing bef non empty\n");
						printf("%d: %lld\n",i-1,pier[i-1][j]);
						printf("%d: %lld\n",i,pier[i][k]);
						printf("prev: %lld\n",prev);
						printf("at:\n");
						printf("     %d: %lld\n",i-2,pier[i-2][pos]);
						printf("     %d: %lld\n",i-1,pier[i-1][j]);
						printf("up: %lld | down: %lld | -> %lld\n",up,down,up-down);
						printf("------> %lld\n\n",up-down+prev);
					}
					
					dec[i][j][k]+=prev;
					dec[i][j][k]+=sum[i][right[i-1][j]]-sum[i][me[i][k]];
				}
			}
			else{
				ll prev=0;
				int pos=0;
				for(int k=0;k<(int)pier[i-2].size();k++){
					ll aux=max(dec[i-1][k][j],inc[i-1][k][j]);
					if(aux>=prev){
						prev=aux;
						pos=k;
					}
				}
				for(int k=0;k<(int)pier[i].size();k++){

					if(deb_inf_state){
						ll up=sum[i-1][left[i][k]];
						ll down=sum[i-1][right[i-2][pos]];
						printf("decreasing bef empty\n");
						printf("%d: %lld\n",i-1,pier[i-1][j]);
						printf("%d: %lld\n",i,pier[i][k]);
						printf("prev: %lld\n",prev);
						printf("at:\n");
						printf("     %d: %lld\n",i-2,pier[i-2][pos]);
						printf("     %d: %lld\n",i-1,pier[i-1][j]);
						if(pier[i][k]>=pier[i-2][pos]){
							printf("up: %lld | down: %lld | -> %lld\n",up,down,up-down);
							printf("------> %lld\n\n",up-down+prev);
						}
						else
							printf("------> %lld\n\n",prev);
					}
					
					dec[i][j][k]+=prev;
					if(pier[i][k]<pier[i-2][pos]) continue;
					dec[i][j][k]+=sum[i-1][left[i][k]]-sum[i-1][right[i-2][pos]];
				}
			}

			//increasing:
			ll prev=0;
			int pos=0;
			for(int k=0;k<(int)pier[i-2].size();k++){
				if(pier[i-2][k]>pier[i-1][j]) break;
				ll aux=inc[i-1][k][j];
				if(!pier[i-2][k]) aux=max(aux,dec[i-1][k][j]);
				if(aux>=prev){
					prev=aux;
					pos=k;
				}
			}
			for(int k=0;k<(int)pier[i].size();k++){

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

	ll res=0;
	for(int i=0;i<(int)pier[n-2].size();i++)
		for(int j=0;j<(int)pier[n-1].size();j++)
			res=max({res,dec[n-1][i][j],inc[n-1][i][j]});
	
	return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 70496 KB Output is correct
2 Correct 146 ms 80292 KB Output is correct
3 Correct 87 ms 58192 KB Output is correct
4 Correct 86 ms 58204 KB Output is correct
5 Correct 327 ms 174724 KB Output is correct
6 Correct 471 ms 177120 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 822 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 85 ms 58188 KB Output is correct
2 Correct 87 ms 58160 KB Output is correct
3 Correct 125 ms 63344 KB Output is correct
4 Correct 122 ms 65736 KB Output is correct
5 Correct 180 ms 77872 KB Output is correct
6 Correct 173 ms 77692 KB Output is correct
7 Correct 179 ms 77708 KB Output is correct
8 Correct 182 ms 77772 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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '8866', found: '7755'
6 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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '8866', found: '7755'
6 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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '8866', found: '7755'
6 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 58188 KB Output is correct
2 Correct 87 ms 58160 KB Output is correct
3 Correct 125 ms 63344 KB Output is correct
4 Correct 122 ms 65736 KB Output is correct
5 Correct 180 ms 77872 KB Output is correct
6 Correct 173 ms 77692 KB Output is correct
7 Correct 179 ms 77708 KB Output is correct
8 Correct 182 ms 77772 KB Output is correct
9 Correct 217 ms 88648 KB Output is correct
10 Correct 133 ms 49612 KB Output is correct
11 Correct 280 ms 101496 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '8866', found: '7755'
15 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 70496 KB Output is correct
2 Correct 146 ms 80292 KB Output is correct
3 Correct 87 ms 58192 KB Output is correct
4 Correct 86 ms 58204 KB Output is correct
5 Correct 327 ms 174724 KB Output is correct
6 Correct 471 ms 177120 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Runtime error 822 ms 2097152 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -