Submission #1186907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186907		ByeWorld	Catfish Farm (IOI22_fish)	C++20	52 / 100	1053 ms	508696 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first 
#define se second
#define pb push_back
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> ipii;
const int MAXN = 5010;
const int MAXA = 3e5+10;
const ll INF = 2e15+10;
void chmx(auto &a, auto b){ a = max(a, b); }
void chmn(auto &a, auto b){ a = min(a, b); }

int n, m;
ll x[MAXA], y[MAXA], w[MAXA], a[MAXN][MAXN];
ll up[MAXN][MAXN], dw[MAXN][MAXN], pr[MAXN][MAXN], 
upmx[MAXN][MAXN], dwmx[MAXN][MAXN];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
	n = N; m = M;
	for(int i=1; i<=m; i++){
		x[i] = X[i-1]+1; y[i] = Y[i-1]+1; w[i] = W[i-1];
		a[x[i]][y[i]] += w[i];
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++) pr[i][j] = pr[i][j-1]+a[i][j];
	}
	
	for(int i=0; i<=n+1; i++)
		for(int j=0; j<=n+1; j++) 
			dw[i][j] = up[i][j] = upmx[i][j] = dwmx[i][j] = -INF;
	dw[0][0] = up[0][0] = 0;
	int i = 0;
		for(int j=0; j<=n; j++){
			upmx[i][j] = max((j==0 ? -INF : upmx[i][j-1]), up[i][j]-pr[i][j] );
		}
		for(int j=n; j>=0; j--){
			dwmx[i][j] = max(dwmx[i][j+1], dw[i][j]+pr[i+1][j] );
		}

	ll ANS = 0;

	for(int i=1; i<=n; i++){
		for(int j=0; j<=n; j++){
			// for(int k=0; k<=j; k++){
			// 	chmx(up[i][j], (up[i-1][k]-pr[i-1][k]) + pr[i-1][j] );
			// }
			// for(int k=j; k<=n; k++){
			// 	chmx(dw[i][j], dw[i-1][k]+pr[i][k] - pr[i][j] );
			// }
			// up[i][j] = up[i-1][k]-pr[i-1][k] + pr[i-1][j];
			up[i][j] = upmx[i-1][j] + pr[i-1][j];
			dw[i][j] = dwmx[i-1][j] - pr[i][j];
		}

		ll MX = 0;
		for(int j=0; j<=n; j++) chmx(MX, max(dw[i-1][j], up[i-1][j]));
		chmx(up[i][0], MX);
		chmx(dw[i][0], MX);

		for(int j=0; j<=n; j++){
			chmx(dw[i][j], up[i][j]);

			chmx(ANS, up[i][j]);
			chmx(ANS, dw[i][j]);
		}

		for(int j=0; j<=n; j++){
			upmx[i][j] = max((j==0 ? 0 : upmx[i][j-1]), up[i][j]-pr[i][j] );
		}
		for(int j=n; j>=0; j--){
			dwmx[i][j] = max(dwmx[i][j+1], dw[i][j]+pr[i+1][j] );
		}
	}
	return ANS;
}

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