oj.uz

Submission #659487

# Submission time Handle Problem Language Result Execution time Memory
659487 2022-11-17T23:35:13 Z pere_gil Catfish Farm (IOI22_fish) C++17
61 / 100
 880 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");
}

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

	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<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][j]];
			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 126 ms 70460 KB Output is correct
2 Correct 150 ms 80308 KB Output is correct
3 Correct 94 ms 58120 KB Output is correct
4 Correct 93 ms 58252 KB Output is correct
5 Correct 365 ms 174800 KB Output is correct
6 Correct 527 ms 177248 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 842 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 89 ms 58268 KB Output is correct
2 Correct 89 ms 58080 KB Output is correct
3 Correct 147 ms 63428 KB Output is correct
4 Correct 135 ms 66484 KB Output is correct
5 Correct 189 ms 79416 KB Output is correct
6 Correct 239 ms 78760 KB Output is correct
7 Correct 189 ms 79416 KB Output is correct
8 Correct 194 ms 79400 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 216 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 1236 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 952 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 2 ms 692 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 216 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 1236 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 952 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 2 ms 692 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 6 ms 3840 KB Output is correct
17 Correct 352 ms 259272 KB Output is correct
18 Correct 335 ms 243320 KB Output is correct
19 Correct 236 ms 169260 KB Output is correct
20 Correct 187 ms 122480 KB Output is correct
21 Correct 191 ms 117192 KB Output is correct
22 Correct 600 ms 444368 KB Output is correct
23 Correct 27 ms 18900 KB Output is correct
24 Correct 206 ms 139684 KB Output is correct
25 Correct 3 ms 980 KB Output is correct
26 Correct 23 ms 15240 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 216 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 1236 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 952 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 2 ms 692 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 6 ms 3840 KB Output is correct
17 Correct 352 ms 259272 KB Output is correct
18 Correct 335 ms 243320 KB Output is correct
19 Correct 236 ms 169260 KB Output is correct
20 Correct 187 ms 122480 KB Output is correct
21 Correct 191 ms 117192 KB Output is correct
22 Correct 600 ms 444368 KB Output is correct
23 Correct 27 ms 18900 KB Output is correct
24 Correct 206 ms 139684 KB Output is correct
25 Correct 3 ms 980 KB Output is correct
26 Correct 23 ms 15240 KB Output is correct
27 Correct 8 ms 2900 KB Output is correct
28 Runtime error 880 ms 2097152 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 58268 KB Output is correct
2 Correct 89 ms 58080 KB Output is correct
3 Correct 147 ms 63428 KB Output is correct
4 Correct 135 ms 66484 KB Output is correct
5 Correct 189 ms 79416 KB Output is correct
6 Correct 239 ms 78760 KB Output is correct
7 Correct 189 ms 79416 KB Output is correct
8 Correct 194 ms 79400 KB Output is correct
9 Correct 212 ms 89992 KB Output is correct
10 Correct 141 ms 51388 KB Output is correct
11 Correct 280 ms 99248 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 240 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 296 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 216 KB Output is correct
18 Correct 85 ms 58208 KB Output is correct
19 Correct 88 ms 58232 KB Output is correct
20 Correct 87 ms 58192 KB Output is correct
21 Correct 106 ms 58204 KB Output is correct
22 Correct 270 ms 96276 KB Output is correct
23 Correct 396 ms 135540 KB Output is correct
24 Correct 379 ms 143128 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 70460 KB Output is correct
2 Correct 150 ms 80308 KB Output is correct
3 Correct 94 ms 58120 KB Output is correct
4 Correct 93 ms 58252 KB Output is correct
5 Correct 365 ms 174800 KB Output is correct
6 Correct 527 ms 177248 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Runtime error 842 ms 2097152 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -