Submission #753724

#	Time	Username	Problem	Language	Result	Execution time	Memory
753724		nicksms	Catfish Farm (IOI22_fish)	C++17	100 / 100	617 ms	108180 KiB

fish

/**
 *      Author:  Nicholas Winschel
 *      Created: 05.09.2023 22:40:58
**/

// screw this problem man. had [most of] the main insights almost immediately, couldn't work out the implementation details (i am allergic to 2 ptrs)
// for over 2 days. just gave up, checked online and someone had a 50 line solution that did pretty much exactly what I expected

// i'm not mad, you're mad.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

#include "fish.h"

// THIS IMPL IS NOT ORIGINAL.
const int MAXN = 1e5+5;
const ll inf = 1e18;
map<int, ll> c[MAXN], blo[MAXN];
vl dp[MAXN];
vi pos[MAXN];
V<pair<int,ll>> pre[MAXN];
ll lsum(int ind, int ub) {
	auto i = lower_bound(pre[ind].begin(),pre[ind].end(), pair<int,ll>{ub+1, -inf});
	if (i == pre[ind].begin()) return 0;
	return (--i)->second;
}

long long max_weights(int N, int M, vi X, vi Y, vi W) {
	for (int i = 0; i < M; i++) 
		c[X[i]+1][Y[i]+1] += W[i], pos[X[i]+1].push_back(Y[i]);
	for (int i = 1; i <= N; i++) {
		sort(pos[i].begin(),pos[i].end()); pos[i].push_back(N);
		ll tot = 0;
		for (auto [po, val] : c[i]) tot += val, pre[i].emplace_back(po,tot);
	}
	for (int j : pos[1]) blo[1][j]=0;
	dp[1]=vl(sz(pos[1]));
	for (int i = 2; i <= N; i++) {
		dp[i].resize(sz(pos[i]));

		// handle case where left is greater
		int l = pos[i-1].size()-1;
		ll bsf = -inf;
		for (int r = sz(pos[i]) - 1; r >= 0; r--) {
			while (l >= 0 && pos[i-1][l] >= pos[i][r])
				bsf = max(bsf, dp[i-1][l] + lsum(i, pos[i-1][l])),--l;
			dp[i][r]=bsf-lsum(i,pos[i][r]);
		}

		auto it = blo[i-1].begin();
		bsf=-inf;
		for (int r = 0; r < sz(pos[i]); r++) {
			while (it != blo[i-1].end() && it->f <= pos[i][r])
				bsf = max(bsf, it->s - lsum(i-1, it->f)),++it;
			dp[i][r]=max(dp[i][r],
							blo[i][pos[i][r]]= bsf + lsum(i-1,pos[i][r])); // why does this work again?
		}
		for (int j = 0; j < sz(pos[i-1]); j++) 
			blo[i][pos[i-1][j]] = max(blo[i][pos[i-1][j]], dp[i-1][j] + lsum(i,pos[i-1][j])); // OH
	}
	ll ret = 0;
	for (ll v : dp[N]) ret = max(ret, v);
	return ret;
}

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