Submission #659195

#	Time	Username	Problem	Language	Result	Execution time	Memory
659195		pere_gil	Catfish Farm (IOI22_fish)	C++17	44 / 100	1199 ms	2097152 KiB

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
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16