Submission #758051

#	Time	Username	Problem	Language	Result	Execution time	Memory
758051		amunduzbaev	메기 농장 (IOI22_fish)	C++17	0 / 100	1136 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 + 1, 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 + 1), suff_tp(n + 1), pref_00(n + 1), suff_11(n + 1), suff_01(n + 1);
	vector<int> mx(n + 1);
	int res = 0;
	
/*	

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++){
			if(4 <= i){
				dp[i][j][0] = mx[i - 3] + pref[i - 1][j];
			}
			dp[i][j][0] = max({pref_tp[j] + pref[i - 1][j - 1], suff_tp[j], pref_00[j] + pref[i - 1][j]});
			dp[i][j][1] = max({suff_11[j] - pref[i][j], (j < n ? suff_01[j + 1] - pref[i][j] : 0)});
			
			tp[i][j] = max(dp[i][j][0], dp[i][j][1]);
			mx[i] = max(mx[i], tp[i][j]);
		}
		
		//~ for(int j=1;j<=n;j++){
			//~ cout<<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>0;j--){
				if(j < n){
					suff_tp[j] = suff_tp[j + 1], suff_11[j] = suff_11[j + 1], suff_01[j] = suff_01[j + 1];
				} else {
					suff_tp[j] = suff_11[j] = suff_01[j] = 0;
				}
				if(i > 1){
					suff_tp[j] = max(suff_tp[j], tp[i - 1][j] + pref[i][j]);
				} 
				suff_11[j] = max(suff_11[j], dp[i][j][1] + pref[i + 1][j]);
				suff_01[j] = max(suff_01[j], dp[i][j][0] + pref[i + 1][j]);
			}
		}
		
		res = max(res, mx[i]);
	}
	
	return res;
}

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