제출 #763968

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

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;

const int MAXN = 305, MAXL = 10;
ll a[MAXN][MAXN], sum[MAXN][MAXN], DP[MAXN][MAXL][MAXL];

ll max_weights(int N, int M, vi X, vi Y, vi W)
{
	if(N <= 300)
	{
		for(int i = 0; i < M; i++)
			a[X[i]][Y[i]] = W[i];
			
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				sum[i][j+1] = sum[i][j] + a[i][j];
				
		for(int i = N - 1; i >= 0; i--)
		{
			for(int pre = 0; pre < MAXL; pre++)
			{
				for(int me = 0; me < MAXL; me++)
				{
					for(int nxt = 0; nxt < MAXL; nxt++)
					{
						if(i == N - 1 && nxt > 0)
							break;
						DP[i][pre][me] = max(DP[i][pre][me],
											 DP[i+1][me][nxt] +
												max(sum[i][max(pre, nxt)+1] - sum[i][me], 0LL));
					}
					// cerr << i << ", " << pre << ", " << me << ": " << DP[i][pre][me] << "\n";
				}
			}
		}
		
		ll ans = 0;
		for(int i = 0; i < MAXL; i++)
			ans = max(ans, DP[0][0][i]);
		return ans;
	}
	return 0;
}

• 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