제출 #1210699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210699		Nicolaikrob	Catfish Farm (IOI22_fish)	C++17	35 / 100	1105 ms	2162688 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
	int sz = n+3;
	vector<vector<ll>> G(sz, vector<ll> (sz, 0)), PS(sz, vector<ll> (sz, 0));
	for(int i = 0; i < m; i++) G[X[i]][Y[i]] = W[i];
	for(int c = 0; c < n; c++) {
		for(int r = 1; r <= n; r++)
			PS[c][r] = PS[c][r-1]+G[c][r-1];
	}
	vector<vector<ll>> higher(sz, vector<ll> (sz, 0)), best(sz, vector<ll> (sz, 0));
	for(int i = 0; i <= n; i++) higher[1][i] = PS[0][i];
	for(int i = 0; i <= n; i++) best[1][i] = max(higher[1][i], PS[1][n]-PS[1][i]);
	for(int c = 2; c < n; c++) {
		for(int r = 0; r <= n; r++) {
			ll bt = 0;
			for(int i = 0; i <= n; i++)
				bt = max(bt, best[c-2][i]+PS[c-1][max(i,r)]);

			for(int i = 0; i <= r; i++)
				bt = max(bt, higher[c-1][i]+PS[c-1][r]-PS[c-1][i]);

			best[c][r] = higher[c][r] = bt;

			for(int i = r; i <= n; i++)
				best[c][r] = max(best[c][r], best[c-1][i]+PS[c][i]-PS[c][r]);
		}
	}
	ll ans = 0;
	for(int i = 0; i <= n; i++)
		ans = max(ans, best[n-1][i]);
	return ans;
}

• 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