Submission #1056004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056004		parsadox2	Catfish Farm (IOI22_fish)	C++17	100 / 100	109 ms	38364 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N = 1e5 + 10;
int n , m , sz[N];
vector <pair<int , int>> all[N];
vector <long long> dp[2][N];

long long max_weights(int nn , int mm , vector <int> X , vector <int> Y , vector <int> W)
{
	n = nn;
	m = mm;
	for(int i = 0 ; i < n ; i++)
		all[i].push_back({0 , 0});
	for(int i = 0 ; i < m ; i++)
		all[X[i]].push_back(make_pair(Y[i] , W[i]));
	for(int i = 0 ; i < n ; i++)
		all[i].push_back({n , 0});
	for(int i = 0 ; i < n ; i++)
	{
		sort(all[i].begin() , all[i].end());
		sz[i] = all[i].size();
		dp[0][i].resize(sz[i] , 0);
		dp[1][i].resize(sz[i] , 0);
	}
	long long ans = 0;
	for(int i = 1 ; i < n ; i++)
	{
		long long mx = 0;
		for(auto u : dp[0][i - 1])
			mx = max(mx , u);
		for(auto u : dp[1][i - 1])
			mx = max(mx , u);
		int pos = 0;
		long long val_down = 0;
		for(int j = 0 ; j < sz[i] ; j++)
		{
			while(pos != sz[i - 1] && all[i - 1][pos].F < all[i][j].F)
			{
				val_down = max(val_down , dp[0][i - 1][pos]);
				val_down += all[i - 1][pos].S;
				pos++;
			}
			dp[0][i][j] = max(dp[0][i][j] , (max(mx , val_down)));
			dp[1][i][j] = max(dp[1][i][j] , (max(mx , val_down)));
		}
		long long val_up = 0;
		pos = sz[i - 1] - 1;
		for(int j = sz[i] - 1 ; j >= 0 ; j--)
		{
			while(pos >= 0 && all[i - 1][pos].F > all[i][j].F)
			{
				val_up = max(val_up , dp[1][i - 1][pos]);
				pos--;
			}
			val_up += all[i][j].S;
			dp[1][i][j] = max(dp[1][i][j] , val_up);
			ans = max(ans , dp[1][i][j]);
			ans = max(ans , dp[0][i][j]);
		}
	}
	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