제출 #1005167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1005167		alex_2008	메기 농장 (IOI22_fish)	C++17	35 / 100	297 ms	894356 KiB

fish

#include "fish.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 3e2 + 10;
ll col_sm[MAX_N][MAX_N];
ll dp[MAX_N][MAX_N][MAX_N];
ll dp_pref[MAX_N][MAX_N][MAX_N];
ll dp_suff[MAX_N][MAX_N][MAX_N];
ll pref_mx[MAX_N][MAX_N][MAX_N];
ll dpp[MAX_N][MAX_N][MAX_N];
ll f(int r, int c) {
	if (r == -1) return 0;
	return col_sm[r][c];
}
ll sm(int c, int r1, int r2) {
	return f(c, r2) - f(c, r1 - 1);
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	for (int i = 0; i < M; i++) {
		col_sm[X[i]][Y[i]] = W[i];
	}
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			col_sm[i][j] += col_sm[i][j - 1];
		}
	}
	//H bardzrutyun => (0, 1, ..., H - 1) bolory vercvac en
	for (int h1 = 0; h1 <= N; h1++) {
		for (int h2 = 0; h2 <= N; h2++) {
			if (h1 >= h2) dp[1][h1][h2] = sm(1, h2, h1 - 1);
			else dp[1][h1][h2] = sm(0, h1, h2 - 1);
			
		}
	}
	//cout << 0 << " " << 0 << " " << 5 << " " << sm(0, 0, 4) << " " << col_sm[0][4] << "\n";
	for (int h1 = 0; h1 <= N; h1++) {
		for (int h2 = 0; h2 <= N; h2++) {
			pref_mx[1][h1][h2] = max(dp[1][h1][h2], pref_mx[1][h1 - 1][h2]);
			if (h1 >= h2) {
				dp_pref[1][h1][h2] = max(dp_pref[1][h1 - 1][h2], dp[1][h1][h2] - sm(1, h2, h1 - 1));
			}
		}
	}
	for (int h1 = N; h1 >= 0; h1--) {
		for (int h2 = 0; h2 <= h1; h2++) {
			dp_suff[1][h1][h2] = max(dp[1][h1][h2], dp_suff[1][h1 + 1][h2]);
		}
	}
	for (int i = 2; i < N; i++) {
		for (int h1 = 0; h1 <= N; h1++) {
			for (int h2 = 0; h2 <= N; h2++) {
				if (h1 >= h2) {
					//dp[i][h1][h2] = max(dp[i - 1][esim][h1] + sm(i, h2, h1 - 1));
					dp[i][h1][h2] = pref_mx[i - 1][N][h1] + sm(i, h2, h1 - 1);
				}
				else {
					//h1 < h2
					//if h3 <= h1 < h2
					dp[i][h1][h2] = pref_mx[i - 1][h1][h1] + sm(i - 1, h1, h2 - 1);
					//if h1 < h2 <= h3
					//dp[i][h1][h2] = max(dp[i - 1][h3][h1] - sm(i, h1, h2 - 1))
					dp[i][h1][h2] = max(dp[i][h1][h2], dp_suff[i - 1][h2][h1]);
					//if h1 < h3 <= h2
					dp[i][h1][h2] = max(dp[i][h1][h2], dp_pref[i - 1][h2][h1] + sm(i - 1, h1, h2 - 1));
				}
			}
		}
		for (int h1 = 0; h1 <= N; h1++) {
			for (int h2 = 0; h2 <= N; h2++) {
				pref_mx[i][h1][h2] = max(dp[i][h1][h2], pref_mx[i][h1 - 1][h2]);
				if (h1 >= h2) {
					dp_pref[i][h1][h2] = max(dp_pref[i][h1 - 1][h2], dp[i][h1][h2] - sm(i, h2, h1 - 1));
				}
			}
		}
		for (int h1 = N; h1 >= 0; h1--) {
			for (int h2 = 0; h2 <= h1; h2++) {
				dp_suff[i][h1][h2] = max(dp[i][h1][h2], dp_suff[i][h1 + 1][h2]);
			}
		}
	}
	//cout << "? " << dp[2][3][3] << "\n";
	ll mx = 0;
	for (int h1 = 0; h1 <= N; h1++) {
		for (int h2 = 0; h2 <= N; h2++) {
			mx = max(mx, dp[N - 1][h1][h2]);
		}
	}
	return mx;
}
/*
int main() {
	//3 2
	//0 0 1
	//1 1 1
	//cout << max_weights(3, 2, { 0, 1 }, { 0, 1 }, { 1, 1 });
	
}
*/

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