제출 #1241596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241596		gs13105	메기 농장 (IOI22_fish)	C++20	70 / 100	86 ms	34116 KiB

fish

#include <bits/stdc++.h>
using namespace std;

#include "fish.h"

int N, M;
vector<int> idx[100010];
int sz[100010];

vector<long long> sum[100010];
vector<long long> up[100010];
vector<long long> down[100010];
long long tot[100010];

void init(vector<int> &X, vector<int> &Y, vector<int> &W)
{
	vector<vector<pair<int, int>>> fish(N);
	for(int i = 0; i < M; i++)
		fish[X[i]].push_back({ Y[i], W[i] });
	for(int i = 0; i < N; i++)
	{
		sz[i] = (int)fish[i].size();
		if(!sz[i])
			continue;
		sort(fish[i].begin(), fish[i].end());
		idx[i].resize(sz[i]);
		sum[i].resize(sz[i]);
		up[i].resize(sz[i]);
		down[i].resize(sz[i]);
		for(int j = 0; j < sz[i]; j++)
		{
			auto [x, y] = fish[i][j];
			idx[i][j] = x;
			sum[i][j] = y;
			if(j)
				sum[i][j] += sum[i][j - 1];
		}
	}
}

long long solve()
{
	tot[0] = 0;
	for(int i = 0; i < sz[0]; i++)
		up[0][i] = sum[0][i];
	for(int i = 1; i < N; i++)
	{
		tot[i] = !sz[i - 1] ? tot[i - 1] : max({ tot[i - 1], down[i - 1].front(), up[i - 1].back() });
		if(!sz[i])
			continue;
		if(!sz[i - 1])
		{
			down[i][0] = tot[i - 1] + sum[i].back();
			continue;
		}

		long long mx = tot[i - 1] + sum[i].back();
		int p = sz[i - 1] - 1, q = sz[i] - 1;
		for(int j = sz[i] - 1; j >= 0; j--)
		{
			while(p >= 0 && idx[i - 1][p] > idx[i][j])
			{
				while(q >= 0 && idx[i][q] >= idx[i - 1][p])
					q--;
				mx = max(mx, down[i - 1][p] + (q >= 0 ? sum[i][q] : 0));
				p--;
			}
			down[i][j] = mx - (j ? sum[i][j - 1] : 0);
		}

		mx = down[i - 1].front();
		p = 0, q = 0;
		for(int j = 0; j < sz[i]; j++)
		{
			while(p < sz[i - 1] && idx[i - 1][p] < idx[i][j])
			{
				while(q < sz[i] && idx[i][q] <= idx[i - 1][p])
					q++;
				mx = max(mx, up[i - 1][p] - (q ? sum[i][q - 1] : 0));
				p++;
			}
			up[i][j] = mx + sum[i][j];
		}
	}

	long long res = tot[N - 1];
	if(sz[N - 1])
		res = max(res, down[N - 1].front());
	return res;
}

long long max_weights(int _N, int _M, vector<int> X, vector<int> Y, vector<int> W)
{
	N = _N;
	M = _M;
	init(X, Y, W);
	return solve();
}

• 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: 0 / 14
• Subtask 8: 0 / 16