Submission #638616

#	Time	Username	Problem	Language	Result	Execution time	Memory
638616		maomao90	Catfish Farm (IOI22_fish)	C++17	100 / 100	309 ms	70680 KiB

fish

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
 
#ifndef DEBUG
#define cerr if (0) cerr
#endif
 
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 100005;
const int MAXM = 300005;

int n, m;
vii fish[MAXN];
vector<pair<int, ll>> dp[2][MAXN];

ll max_weights(int N, int M, vi X, vi Y, vi W) {
    n = N; m = M;
    REP (i, 0, m) {
	X[i]++; Y[i]++;
	fish[X[i]].pb({Y[i], W[i]});
    }
    REP (i, 1, n + 1) {
	sort(ALL(fish[i]));
    }
    dp[0][0].pb({0, 0});
    dp[1][0].pb({0, 0});
    REP (i, 1, n + 1) {
	vi cand;
	for (auto [y, w] : fish[i - 1]) {
	    cand.pb(y);
	}
	for (auto [y, w] : fish[i]) {
	    cand.pb(y - 1);
	}
	for (auto [y, w] : fish[i + 1]) {
	    cand.pb(y);
	}
	cand.pb(0);
	sort(ALL(cand));
	cand.resize(unique(ALL(cand)) - cand.begin());
	REP (z, 0, 2) {
	    REP (j, 0, SZ(cand)) {
		dp[z][i].pb({cand[j], 0});
	    }
	}
	{ // .^
	    auto fptr = fish[i - 1].begin();
	    auto fdptr = fish[i - 1].begin();
	    auto dptr = dp[0][i - 1].begin();
	    ll sm = 0;
	    ll sub = 0;
	    ll mx = 0;
	    REP (j, 0, SZ(cand)) {
		while (fptr != fish[i - 1].end() && fptr -> FI <= cand[j]) {
		    sm += fptr -> SE;
		    ++fptr;
		}
		while (dptr != dp[0][i - 1].end() && dptr -> FI <= cand[j]) {
		    while (fdptr != fish[i - 1].end() && fdptr -> FI <= dptr -> FI) {
			sub += fdptr -> SE;
			++fdptr;
		    }
		    mxto(mx, dptr -> SE - sub);
		    ++dptr;
		}
		mxto(dp[0][i][j].SE, mx + sm);
		mxto(dp[1][i][j].SE, mx + sm);
	    }
	}
	{ // ^.
	    ll sm = 0;
	    auto fdptr = fish[i].begin();
	    auto fptr = fish[i].begin();
	    auto dptr = dp[1][i - 1].end();
	    while (fdptr != fish[i].end() && fdptr -> FI <= prev(dptr) -> FI) {
		sm += fdptr -> SE;
		++fdptr;
	    }
	    ll sub = 0;
	    while (fptr != fish[i].end() && fptr -> FI <= cand.back()) {
		sub += fptr -> SE;
		fptr++;
	    }
	    ll mx = 0;
	    RREP (j, SZ(cand) - 1, 0) {
		while (fptr != fish[i].begin() && prev(fptr) -> FI > cand[j]) {
		    --fptr;
		    sub -= fptr -> SE;
		}
		while (dptr != dp[1][i - 1].begin() && prev(dptr) -> FI >= cand[j]) {
		    --dptr;
		    while (fdptr != fish[i].begin() && prev(fdptr) -> FI > dptr -> FI) {
			--fdptr;
			sm -= fdptr -> SE;
		    }
		    mxto(mx, dptr -> SE + sm);
		}
		mxto(dp[1][i][j].SE, mx - sub);
	    }
	}
	{ // ._^
	    auto fptr = fish[i - 1].begin();
	    auto dptr = dp[1][i - 2].begin();
	    ll sm = 0;
	    ll mx = 0;
	    REP (j, 0, SZ(cand)) {
		while (fptr != fish[i - 1].end() && fptr -> FI <= cand[j]) {
		    sm += fptr -> SE;
		    ++fptr;
		}
		while (dptr != dp[1][i - 2].end() && dptr -> FI <= cand[j]) {
		    mxto(mx, dptr -> SE);
		    ++dptr;
		}
		mxto(dp[0][i][j].SE, mx + sm);
		mxto(dp[1][i][j].SE, mx + sm);
	    }
	}
	{ // ^_.
	    ll sm = 0;
	    auto fdptr = fish[i - 1].begin();
	    auto dptr = dp[1][i - 2].end();
	    while (fdptr != fish[i - 1].end() && fdptr -> FI <= prev(dptr) -> FI) {
		sm += fdptr -> SE;
		++fdptr;
	    }
	    ll mx = 0;
	    RREP (j, SZ(cand) - 1, 0) {
		while (dptr != dp[1][i - 2].begin() && prev(dptr) -> FI >= cand[j]) {
		    --dptr;
		    while (fdptr != fish[i - 1].begin() && prev(fdptr) -> FI > dptr -> FI) {
			--fdptr;
			sm -= fdptr -> SE;
		    }
		    mxto(mx, dptr -> SE + sm);
		}
		mxto(dp[0][i][j].SE, mx);
		mxto(dp[1][i][j].SE, mx);
	    }
	}
	cerr << i << ' ' << 0 << '\n';
	for (auto [y, v] : dp[0][i]) {
	    cerr << ' ' << y << ' ' << v << '\n';
	}
	cerr << i << ' ' << 1 << '\n';
	for (auto [y, v] : dp[1][i]) {
	    cerr << ' ' << y << ' ' << v << '\n';
	}
    }
    ll ans = 0;
    for (auto [y, v] : dp[1][n]) {
	mxto(ans, v);
    }
    return ans;
}

• 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