Submission #1235028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235028		AMnu	Catfish Farm (IOI22_fish)	C++20	100 / 100	149 ms	33308 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 1e5+5;

struct dp {
	int pos;
	ll val, inc, dec;
};

vector <dp> F[MAXN];

bool cmp(dp x,dp y) {
	if (x.pos != y.pos) return x.pos < y.pos;
	return x.val < y.val;
}

ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
	for (int i=0;i<M;i++) {
		F[X[i]].push_back({Y[i],W[i],0,0});
	}
	for (int i=0;i<N;i++) {
		F[i].push_back({0,0});
		F[i].push_back({N,0});
		sort(F[i].begin(),F[i].end(),cmp);
		for (int j=1;j<(int)F[i].size();j++) {
			F[i][j].val += F[i][j-1].val;
		}
		for (int j=F[i].size()-1;j>0;j--) {
			F[i][j].val = F[i][j-1].val;
		}
	}
	for (int i=1;i<N;i++) {
		for (int j=0,k=0;j<(int)F[i].size();j++) {
			while (k < (int)F[i-1].size() && F[i-1][k].pos <= F[i][j].pos) {
				F[i][j].inc = max(F[i][j].inc,
					F[i-1][k].inc - F[i-1][k].val);
				k++;
			}
			if (j+1<(int)F[i].size()) {
				F[i][j+1].inc = F[i][j].inc;
			}
		}
		for (int j=0,jj=0;j<(int)F[i].size();j++) {
			while (F[i-1][jj].pos < F[i][j].pos) jj++;
			F[i][j].inc += F[i-1][jj].val;
		}
		for (int j=F[i].size()-1,k=F[i-1].size()-1,kk=F[i].size()-1;j>=0;j--) {
			while (k >= 0 && F[i-1][k].pos >= F[i][j].pos) {
				while (kk && F[i][kk-1].pos >= F[i-1][k].pos) kk--;
				F[i][j].dec = max(F[i][j].dec,
					max(F[i-1][k].dec,F[i-1][k].inc) + F[i][kk].val);
				k--;
			}
			if (j) {
				F[i][j-1].dec = F[i][j].dec;
			}
		}
		for (int j=0;j<(int)F[i].size();j++) {
			F[i][j].dec -= F[i][j].val;
		}
		if (i < 2) continue;
		ll opt = 0;
		for (int j=F[i].size()-1,k=F[i-2].size()-1,kk=F[i-1].size()-1;j>=0;j--) {
			while (k >= 0 && F[i-2][k].pos >= F[i][j].pos) {
				while (kk && F[i-1][kk-1].pos >= F[i-2][k].pos) kk--;
				opt = max(opt, max(F[i-2][k].inc,F[i-2][k].dec) + F[i-1][kk].val);
				k--;
			}
			F[i][j].inc = max(F[i][j].inc,opt);
		}
		opt = 0;
		for (int j=0,jj=0,k=0;j<(int)F[i].size();j++) {
			while (F[i-1][jj].pos < F[i][j].pos) jj++;
			while (k < (int)F[i-2].size() && F[i-2][k].pos <= F[i][j].pos) {
				opt = max(opt,max(F[i-2][k].inc,F[i-2][k].dec));
				k++;
			}
			F[i][j].inc = max(F[i][j].inc, opt + F[i-1][jj].val);
		}
	}
	ll ans = 0;
	for (dp x : F[N-1]) {
		ans = max(ans,max(x.inc,x.dec));
	}
	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