제출 #1056610

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

fish

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "fish.h"

int MAX_H = 15;

ll max_weights(int N, int M, vector<int> X_g, vector<int> Y_g, vector<int> W_g) {
	MAX_H = min(MAX_H, N);
	// precompute all range increasing / decreasing
	vector<vi> a(N, vi(N, 0));
	for (int i = 0; i < M; i++) {
		a[X_g[i]][Y_g[i]] += W_g[i];
	}
	vector<vi> pfs(N, vi(N + 1, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 1; j <= N; j++) {
			pfs[i][j] = pfs[i][j - 1] + a[i][j - 1];
		}
	}
/*	cout<<"a: "<<endl;
	for (vi v : a) {
		for (int x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<vector<vi>> inc(N, vector<vi>(N, vi(MAX_H + 1, 0)));
	// inc[i][j][k] (i < j): max sum of going up on [i, j]
	// only considering [0, k - 1]
	vector<vector<vi>> dec(N, vector<vi>(N, vi(MAX_H + 1, 0)));
	// dec[i][j][k] (i < j): max sum of going down on [i, j]
	// only considering [k, MAX_H - 1]
	for (int i = 0; i < N; i++) {	// left pos
		// compute for [i, i]
		inc[i][i][0] = 0;
		dec[i][i][MAX_H] = 0;
		for (int j = 1; j <= MAX_H; j++) {
			inc[i][i][j] = inc[i][i][j - 1] + a[i][j - 1];
		}
		for (int j = MAX_H - 1; j >= 0; j--) {
			dec[i][i][j] = dec[i][i][j + 1] + a[i][j];
		}
		for (int j = i + 1; j < N; j++) {	// [i, j], inclusive
			for (int k = 0; k <= MAX_H; k++) {	// min / max height is k
				for (int l = 0; l <= k; l++) {	// increasing
					// use [l, k-1] for new coln
					inc[i][j][k] = max(inc[i][j][k], inc[i][j - 1][l] + (pfs[j][k] - pfs[j][l]));
				}
				for (int l = k; l <= MAX_H; l++) {	// decreasing
					// use [k, l-1] for new coln
					dec[i][j][k] = max(dec[i][j][k], dec[i][j - 1][l] + (pfs[j][l] - pfs[j][k]));
				}
			}
		}
	}
	vector<vi> incr(N, vi(N, 0));
	vector<vi> decr(N, vi(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			incr[i][j] = inc[i][j][MAX_H];
			decr[i][j] = dec[i][j][0];
		}
	}
/*	cout<<"incr: "<<endl;
	for (vi v : incr) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}
	cout<<"decr: "<<endl;
	for (vi v : decr) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/

	vector<vi> dp(N, vi(2, 0));
	// dp[i][j]: maximum sum until i (exclusive) given last coln type j
	// j = 0: increasing ended; j = 1: decreasing ended
	// only inc can follow dec without skip; rest all need skip
	// can only start w/ inc or blank
	// can only end w/ dec or blank
	dp[0][0] = incr[0][0];
	dp[0][1] = -1e18;
	for (int i = 1; i < N; i++) {
		// compute dp[i][0]
		dp[i][0] = incr[0][i];	// nothing else
		for (int j = 0; j < i; j++) {	// prev was decr
			// start new incr at j+1
			dp[i][0] = max(dp[i][0], dp[j][1] + incr[j + 1][i]);
		}
		for (int j = 1; j < i; j++) {	// prev was incr
			// need to skip j to start new incr at j+1
			dp[i][0] = max(dp[i][0], dp[j - 1][0] + incr[j + 1][i]);
		}
		// compute dp[i][1]
		dp[i][1] = decr[1][i];
		for (int j = 1; j < i; j++) {	// prev was incr
			dp[i][1] = max(dp[i][1], dp[j - 1][0] + decr[j + 1][i]);
		}
		for (int j = 1; j < i; j++) {	// prev was decr
			dp[i][1] = max(dp[i][1], dp[j - 1][1] + decr[j + 1][i]);
		}
	}
/*	cout<<"dp: "<<endl;
	for (int i = 0; i < N; i++) {
		cout<<dp[i][0]<<", "<<dp[i][1]<<endl;
	}*/
	ll ans = 0;
	for (int i = 0; i < N - 1; i++) {
		ans = max(ans, dp[i][0]);
	}
	for (int i = 1; i < N; i++) {
		ans = max(ans, dp[i][1]);
	}
	return ans;
}

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