Submission #659032

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
659032	2022-11-16T00:40:42 Z	pere_gil	Catfish Farm (IOI22_fish)	C++17	44 / 100	943 ms	2097152 KB

fish

#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
             
typedef long long ll;
         
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
	int h=0;
	for(int i=0;i<m;i++) h=max(h,y[i]);
	h+=2;
     
	ll fish[n][h]; memset(fish,0,sizeof fish);
	for(int i=0;i<m;i++) fish[x[i]][y[i]+1]=w[i];
	for(int i=0;i<n;i++)
		for(int j=1;j<h;j++)
			fish[i][j]+=fish[i][j-1];
     
	ll dp[n][2][h][h]; memset(dp,0,sizeof dp);

	for(int i=0;i<h;i++){
		for(int j=0;j<h;j++){
			ll act=0;
			if(i>=j) act+=fish[1][i]-fish[1][j];
			else act+=fish[0][j]-fish[0][i];
			dp[1][0][i][j]=dp[1][1][i][j]=act;
		}
	}
	
	for(int i=2;i<n;i++){
		for(int j=0;j<h;j++){
     
			// decreasing:
			ll prev=0;
			int pos=0;
			for(int k=h-1;k>=j;k--){
				ll aux=max(dp[i-1][0][k][j],dp[i-1][1][k][j]);
				// hmmmm
				if(aux>=prev){
					pos=k;
					prev=aux;
				}
			}
    			
			if(j){
				for(int k=0;k<=j;k++){
					dp[i][0][j][k]+=prev;
					dp[i][0][j][k]+=fish[i][j]-fish[i][k];
				}
			}
			else{
				for(int k=0;k<h;k++){
					dp[i][0][j][k]+=prev;
					if(k>pos) dp[i][0][j][k]+=fish[i-1][k]-fish[i-1][pos];
				}
			}
    			
			// increasing:
			prev=0;
			for(int k=0;k<=j;k++){
				prev=max(prev,dp[i-1][1][k][j]);
				if(!k) prev=max(prev,dp[i-1][0][k][j]);
			}
			for(int k=0;k<h;k++){
				dp[i][1][j][k]+=prev;
    				
				if(j>=k) dp[i][1][j][k]+=fish[i][j]-fish[i][k];
				else dp[i][1][j][k]+=fish[i-1][k]-fish[i-1][j];
			}
		}
	}

	/*
	for(int i=0;i<n;i++){
		for(int j=0;j<h;j++){
			for(int k=0;k<h;k++){
				printf("%d:\n",i);
				printf("decreasing:\n");
				printf("%d %d -> %lld\n",j,k,dp[i][0][j][k]);
				printf("increasing:\n");
				printf("%d %d -> %lld\n",j,k,dp[i][1][j][k]);
				printf("\n");
			}
		}
	}
	*/
     
	ll res=0;
	for(int i=0;i<h;i++)
		for(int j=0;j<h;j++)
			res=max({res,dp[n-1][0][i][j],dp[n-1][1][i][j]});
    	
	return res;
}

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	943 ms	2097152 KB	Execution killed with signal 9
2	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	814 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	7 ms	8020 KB	Output is correct
2	Correct	6 ms	8020 KB	Output is correct
3	Correct	20 ms	8504 KB	Output is correct
4	Correct	17 ms	9556 KB	Output is correct
5	Correct	39 ms	11568 KB	Output is correct
6	Correct	27 ms	11316 KB	Output is correct
7	Correct	31 ms	11552 KB	Output is correct
8	Correct	32 ms	11572 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	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	748 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	696 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	468 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	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	748 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	696 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	319 ms	423580 KB	Output is correct
16	Correct	6 ms	7124 KB	Output is correct
17	Correct	337 ms	428364 KB	Output is correct
18	Correct	339 ms	428224 KB	Output is correct
19	Correct	330 ms	428324 KB	Output is correct
20	Correct	345 ms	428352 KB	Output is correct
21	Correct	90 ms	109612 KB	Output is correct
22	Correct	355 ms	430148 KB	Output is correct
23	Correct	369 ms	426788 KB	Output is correct
24	Correct	325 ms	427796 KB	Output is correct
25	Correct	2 ms	2260 KB	Output is correct
26	Correct	318 ms	426848 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	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	748 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	696 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	319 ms	423580 KB	Output is correct
16	Correct	6 ms	7124 KB	Output is correct
17	Correct	337 ms	428364 KB	Output is correct
18	Correct	339 ms	428224 KB	Output is correct
19	Correct	330 ms	428324 KB	Output is correct
20	Correct	345 ms	428352 KB	Output is correct
21	Correct	90 ms	109612 KB	Output is correct
22	Correct	355 ms	430148 KB	Output is correct
23	Correct	369 ms	426788 KB	Output is correct
24	Correct	325 ms	427796 KB	Output is correct
25	Correct	2 ms	2260 KB	Output is correct
26	Correct	318 ms	426848 KB	Output is correct
27	Runtime error	819 ms	2097152 KB	Execution killed with signal 9
28	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	8020 KB	Output is correct
2	Correct	6 ms	8020 KB	Output is correct
3	Correct	20 ms	8504 KB	Output is correct
4	Correct	17 ms	9556 KB	Output is correct
5	Correct	39 ms	11568 KB	Output is correct
6	Correct	27 ms	11316 KB	Output is correct
7	Correct	31 ms	11552 KB	Output is correct
8	Correct	32 ms	11572 KB	Output is correct
9	Runtime error	757 ms	2097152 KB	Execution killed with signal 9
10	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	943 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #659032

Compilation message