제출 #755014

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

fish

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

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

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
//#define ld long double
#define ull unsigned long long
 
using namespace std;
const int maxn=3e5+10,LOG=17,mod=1e9+7;
int block = 650, timer = 0;
const double eps = 1e-9;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
#define bt(i) (1 << (i))
//#define int ll
const long double inf=2e18;
#define y1 yy
#define pii pair <int, int>

int n, m, x[maxn], y[maxn], w[maxn];
ll a[3010][3010], pref[3010][3010], dp2[3010][3010];
ll dp[3010][3010], Dp[3010], ans;

long long max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W)
{
	n = N;
	m = M;
	forn(1, i, m)
	{
		x[i] = X[i-1]+1;
		y[i] = Y[i-1]+1;
		w[i] = W[i-1];
		a[x[i]][y[i]] = w[i];
	}
	forn(1, i, n)
	{
		forn(1, j, n)
		{
			pref[i][j] = pref[i][j - 1] + a[i][j];
		}
	}
	forn(1, i, n)
	{
		dp[0][i] = -inf;
	}
	forn(1, i, n)
	{
		ll tek = 0;
		if(i >= 2)
		{
			forn(1, j, n)
			{
				tek = max(tek, dp[i-1][j] - pref[i-1][j]);
				dp[i][j] = max(dp[i][j], pref[i-1][j] + tek);
			}
		}
//		forn(1, j, n)
//			cout << dp[i][j] << " ";
//		cout << endl;
		if(i >= 2)
		{
			tek = 0;
			forn(1, j, n)
			{
				tek = max(tek, dp[i-2][j]);
				dp[i][j] = max(dp[i][j], pref[i-1][j] + tek);
			}
		}
		if(i >= 3)
		{
			tek = 0;
			nfor(1, j, n)
			{
				dp[i][j] = max(dp[i][j], tek - pref[i-1][j]);
				tek = max(tek, dp[i-2][j] + pref[i-1][j]);
			}
		}
		if(i >= 3)
		{
			forn(1, j, n)
			{
				dp[i][j] = max(Dp[i-3] + pref[i-1][j], dp[i][j]);
			}
		}
		tek = -inf;
		nfor(1, j, n)
		{
			dp2[i][j] = max(dp2[i][j], tek - pref[i][j]);
//			cout << i << "  " << dp2[i][j] << " " << tek <<  endl;
			tek = max(tek, max(dp2[i-1][j], dp[i-1][j]) + pref[i][j]);
			Dp[i] = max(Dp[i], dp2[i][j] + pref[i+1][j]);
		}
		forn(1, j, n)
		{
			Dp[i] = max(Dp[i], dp[i][j] + pref[i+1][j]);
		}
		ans = max(ans, Dp[i]);
//		cout << Dp[i] << " " << i << endl;
	}
	return ans;
}

• 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