Submission #659195

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
659195	2022-11-17T01:24:49 Z	pere_gil	Catfish Farm (IOI22_fish)	C++17	44 / 100	1000 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=j;k<h;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	Execution timed out	1199 ms	1904432 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Runtime error	915 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	7 ms	8020 KB	Output is correct
3	Correct	20 ms	9564 KB	Output is correct
4	Correct	19 ms	9580 KB	Output is correct
5	Correct	33 ms	12088 KB	Output is correct
6	Correct	28 ms	11440 KB	Output is correct
7	Correct	34 ms	11952 KB	Output is correct
8	Correct	33 ms	11980 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	0 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	212 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	212 KB	Output is correct
8	Correct	1 ms	216 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Correct	1 ms	440 KB	Output is correct
12	Correct	1 ms	724 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	568 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	0 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	212 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	212 KB	Output is correct
8	Correct	1 ms	216 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Correct	1 ms	440 KB	Output is correct
12	Correct	1 ms	724 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	568 KB	Output is correct
15	Correct	362 ms	423692 KB	Output is correct
16	Correct	5 ms	7252 KB	Output is correct
17	Correct	353 ms	428392 KB	Output is correct
18	Correct	345 ms	428336 KB	Output is correct
19	Correct	357 ms	428328 KB	Output is correct
20	Correct	345 ms	428328 KB	Output is correct
21	Correct	95 ms	109440 KB	Output is correct
22	Correct	368 ms	430016 KB	Output is correct
23	Correct	351 ms	426992 KB	Output is correct
24	Correct	336 ms	427616 KB	Output is correct
25	Correct	2 ms	2232 KB	Output is correct
26	Correct	348 ms	426844 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	0 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	212 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	212 KB	Output is correct
8	Correct	1 ms	216 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Correct	1 ms	440 KB	Output is correct
12	Correct	1 ms	724 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	568 KB	Output is correct
15	Correct	362 ms	423692 KB	Output is correct
16	Correct	5 ms	7252 KB	Output is correct
17	Correct	353 ms	428392 KB	Output is correct
18	Correct	345 ms	428336 KB	Output is correct
19	Correct	357 ms	428328 KB	Output is correct
20	Correct	345 ms	428328 KB	Output is correct
21	Correct	95 ms	109440 KB	Output is correct
22	Correct	368 ms	430016 KB	Output is correct
23	Correct	351 ms	426992 KB	Output is correct
24	Correct	336 ms	427616 KB	Output is correct
25	Correct	2 ms	2232 KB	Output is correct
26	Correct	348 ms	426844 KB	Output is correct
27	Runtime error	865 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	7 ms	8020 KB	Output is correct
3	Correct	20 ms	9564 KB	Output is correct
4	Correct	19 ms	9580 KB	Output is correct
5	Correct	33 ms	12088 KB	Output is correct
6	Correct	28 ms	11440 KB	Output is correct
7	Correct	34 ms	11952 KB	Output is correct
8	Correct	33 ms	11980 KB	Output is correct
9	Runtime error	858 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	Execution timed out	1199 ms	1904432 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #659195

Compilation message