제출 #758178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758178		amunduzbaev	메기 농장 (IOI22_fish)	C++17	52 / 100	765 ms	2097152 KiB

fish

    #include "fish.h"
     
    #include "bits/stdc++.h"
    using namespace std;
     
    #ifndef EVAL
    #include "grader.cpp"
    #endif
     
    #define ar array
    typedef int32_t ii;
    typedef long long ll;
    #define int ll
     
    /*
     
    5 4
    0 2 5
    1 1 2
    4 4 1
    3 3 3
     
    */
     
    int max_weights(ii n, ii m, vector<ii> x, vector<ii> y, vector<ii> w) {
    	
    	vector<vector<int>> a(n + 1, vector<int>(n + 1));
    	for(int i=0;i<m;i++){
    		x[i]++, y[i]++;
    		a[x[i]][y[i]] = w[i];
    	}
    	
    	vector<vector<ar<int, 2>>> dp(n + 1, vector<ar<int, 2>>(n + 1, {0, 0}));
    	vector<vector<int>> pref(n + 2, vector<int>(n + 1));
    	vector<vector<int>> tp(n + 1, vector<int>(n + 1));
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			pref[i][j] = pref[i][j-1] + a[i][j];
    		}
    	}
    	vector<int> pref_tp(n + 2), suff_tp(n + 2), pref_00(n + 2), suff_11(n + 2), suff_01(n + 2);
    	vector<int> mx(n + 1);
    	
    /*	
     
    5 4
    0 2 5
    1 1 2
    4 4 1
    3 3 3
     
    */
    	
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			dp[i][j][0] = pref[i - 1][j];
    			if(3 <= i) dp[i][j][0] += mx[i - 3];
    			
    			//~ for(int k=1;k<=n;k++){
    				//~ if(1 < i && k <= j){
    					//~ dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][0] - pref[i - 1][k] + pref[i - 1][j]);
    				//~ }
    				//~ if(2 < i){
    					//~ dp[i][j][0] = max(dp[i][j][0], tp[i - 2][k] + pref[i - 1][max(j, k)]);
    				//~ }
    				//~ if(1 < i && j <= k){
    					//~ dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][1] + pref[i][k] - pref[i][j]);
    					//~ if(j < k){
    						//~ dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][0] + pref[i][k] - pref[i][j]);
    					//~ }
    				//~ }
    			//~ }
    			
    			//~ ar<int, 2> tmp {};
    			//~ tmp[0] = pref[i - 1][j];
    			//~ if(3 <= i) tmp[0] += mx[i - 3];
    			if(i > 1){
    				dp[i][j][0] = max(dp[i][j][0], pref_00[j] + pref[i - 1][j]);
    				dp[i][j][1] = max(dp[i][j][1], suff_11[j] - pref[i][j]);
    				dp[i][j][1] = max(dp[i][j][1], suff_01[j + 1] - pref[i][j]);
    				//~ tmp[0] = max(tmp[0], pref_00[j] + pref[i - 1][j]);
    				//~ tmp[1] = max(tmp[1], suff_11[j] - pref[i][j]);
    				//~ tmp[1] = max(tmp[1], suff_01[j + 1] - pref[i][j]);
    			}
    			if(i > 2){
    				dp[i][j][0] = max(dp[i][j][0], pref_tp[j] + pref[i - 1][j]);
    				dp[i][j][0] = max(dp[i][j][0], suff_tp[j]);
    				//~ tmp[0] = max(tmp[0], pref_tp[j] + pref[i - 1][j]);
    				//~ tmp[0] = max(tmp[0], suff_tp[j]);
    			}
    			
    			//~ cout<<tmp[1]<<" ";
    			//~ assert(tmp[0] == dp[i][j][0]);
    			
    			tp[i][j] = max(dp[i][j][0], dp[i][j][1]);
    			mx[i] = max(mx[i], tp[i][j]);
    		}
    		
    		//~ cout<<"\n";
    		if(i < n){
              for(int j=1;j<=n;j++){
                  mx[i] = max(mx[i], tp[i][j] + pref[i + 1][j]);

                  if(i > 1){
                      pref_tp[j] = max(pref_tp[j - 1], tp[i - 1][j]);
                  } 
                  pref_00[j] = max(pref_00[j - 1], dp[i][j][0] - pref[i][j]);
              }
              for(int j=n;j>=1;j--){
                  if(i > 1){
                      suff_tp[j] = max(suff_tp[j + 1], tp[i - 1][j] + pref[i][j]);
                  } 

                  suff_11[j] = max(suff_11[j + 1], dp[i][j][1] + pref[i + 1][j]);
                  suff_01[j] = max(suff_01[j + 1], dp[i][j][0] + pref[i + 1][j]);
              }
            }
    		
    		//~ for(int j=1;j<=n;j++){
    			//~ cout<<suff_11[j]<<" ";
    		//~ }
    		//~ cout<<"\n";
    		
    		mx[i] = max(mx[i-1], mx[i]);
    	}
    	
    	//~ cout<<"\n";
    	//~ for(int i=1;i<=n;i++){
    		//~ for(int j=1;j<=n;j++){
    			//~ cout<<dp[i][j][1]<<" ";
    		//~ }
    		//~ cout<<"\n";
    	//~ }
    	//~ cout<<"\n";
     
    	return mx[n];
    }

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16