제출 #1231823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231823		RakhimovAmir	메기 농장 (IOI22_fish)	C++17	0 / 100	29 ms	6468 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 301;
ll d[N][N][2], f[N][N], mxs[N][N], mxp[N][N], suff[N][N], mxd[N][N], pref[N][N], mxdd[N];
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	ll res = 0;
	for (ll i = 0; i < N; i++) {
		for (ll j = 0; j < N; j++) {	
			d[i][j][0] = d[i][j][1] = f[i][j] = 0;
		}
	}
	for (ll i = 0; i < M; i++) {
		f[X[i]][Y[i]] = W[i];
	}
	for (ll j = 0; j < N; j++) {
		pref[0][j] = f[0][j];
		if (j)
			pref[0][j] += pref[0][j - 1];
		mxp[0][j] = pref[0][j];
		if (j)
			mxp[0][j] = max(mxp[0][j - 1], mxp[0][j]);
	}
	for (ll j = N - 1; j >= 0; j--) {
		suff[0][j] = (j == N - 1 ? 0 : suff[0][j + 1]) + f[0][j];
	}
	for (ll j = 0; j < N; j++) {
		mxs[0][j] = d[0][j][0] + suff[0][j + 1];
		if (j)
			mxs[0][j] = max(mxs[0][j - 1], mxs[0][j]);
		mxdd[j] = pref[0][j];
	}
	for (ll i = 1; i < N; i++) {
		for (ll j = 0; j < N; j++) {
			pref[i][j] = f[i][j];
			if (j)
				pref[i][j] += pref[i][j - 1];
			mxp[i][j] = pref[i][j] + max(d[i - 1][j][0], d[i - 1][j][1]);
			if (j)
				mxp[i][j] = max(mxp[i][j - 1], mxp[i][j]);
		}
		for (ll j = N - 1; j >= 0; j--) {
			suff[i][j] = (j == N - 1 ? 0 : suff[i][j + 1]) + f[i][j];
		}
		for (ll j = 0; j < N; j++) {
			d[i][j][0] = max(d[i][j][0], mxs[i - 1][j] - suff[i - 1][j + 1]);
			if (i > 1)
				d[i][j][0] = max(d[i][j][0], mxd[i - 2][j] + pref[i - 1][j]);
			d[i][j][0] = max(d[i][j][0], mxdd[i - 1]);
			d[i][j][1] = max(d[i][j][1], mxp[i][N - 1] - pref[i][j]);
			// cout << d[i][j][0] << " " << d[i][j][1] << "\n";
			res = max({res, d[i][j][0], d[i][j][1]});
		}
		for (ll j = 0; j < N; j++) {
			mxs[i][j] = d[i][j][0] + suff[i][j + 1];
			if (j)
				mxs[i][j] = max(mxs[i][j - 1], mxs[i][j]);
		}
		for (ll j = 0; j < N; j++) {
			mxd[i][j] = max(d[i][j][0], d[i][j][1]);
			if (j)
				mxd[i][j] = max(mxd[i][j - 1], mxd[i][j]);
		}
		for (ll j = 0; j < N; j++) {
			mxdd[i] = max(mxdd[i], max(d[i - 1][j][0], d[i - 1][j][1]) + pref[i][j]);
		}
	}
	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