Submission #755228

#	Time	Username	Problem	Language	Result	Execution time	Memory
755228		Red_Inside	Catfish Farm (IOI22_fish)	C++17	100 / 100	482 ms	101872 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

//#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
//#define ld long double
#define ull unsigned long long
 
using namespace std;
const int maxn=3e5+10,LOG=17,mod=1e9+7;
int block = 650, timer = 0;
const double eps = 1e-9;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
#define bt(i) (1 << (i))
//#define int ll
const long long inf=2e18;
#define y1 yy
#define pii pair <int, int>

ll n, m, x[300100], y[300100], w[300100];
ll Dp[100100], ans;
vector <pii> vec[100100];
vector <ll> dp[maxn], dp2[maxn], pref[maxn], pos[maxn];

long long max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W)
{
	n = N;
	m = M;
	forn(1, i, m)
	{
		x[i] = X[i-1]+1;
		y[i] = Y[i-1]+1;
		w[i] = W[i-1];
		vec[x[i]].pb({y[i], w[i]});
	}
	forn(1, i, n) sort(all(vec[i]));
	forn(1, i, n)
	{
		int u1 = 0;
		int u2 = 0;
		int u3 = 0;
		while(u1 < (int)vec[i-1].size() || u2 < (int)vec[i].size() || 
		u3 < (int)vec[i+1].size())
		{
			int f1 = (u1 < (int)vec[i-1].size() ? vec[i-1][u1].f : n+1);
			int f2 = (u2 < (int)vec[i].size() ? vec[i][u2].f : n+1);
			int f3 = (u3 < (int)vec[i+1].size() ? vec[i+1][u3].f : n+1);
			pos[i].pb(min({f1, f2, f3}));
			pref[i].pb((int)pref[i].size() ? pref[i].back() : 0);
			dp[i].pb(0);
			dp2[i].pb(0);
			if(min({f1, f2, f3}) == f1)
				u1++;
			if(min({f1, f2, f3}) == f2)
			{
				pref[i].back() += vec[i][u2].s;
				u2++;
			}
			if(min({f1, f2, f3}) == f3)
				u3++;
		}
	}
	FOR(0, i, (int)dp[0].size())
	{
		dp[0][i] = -inf;
	}
	forn(1, i, n)
	{
		ll tek = 0;
		if(i >= 2)
		{
			int uk = -1;
			tek = 0;
			FOR(0, j, (int)pos[i].size())
			{
				//pointer <= j
				while(uk+1<(int)pos[i-1].size() && pos[i-1][uk+1] <= pos[i][j])
				{
					++uk;
					tek = max(tek, dp[i-1][uk] - pref[i-1][uk]);
				}
				int temp = upper_bound(all(pos[i-1]), pos[i][j]) - pos[i-1].begin()-1;
				dp[i][j] = max(dp[i][j], (temp>=0?pref[i-1][temp]:0) + tek);
			}
		}
		if(i >= 2)
		{
			int uk = -1;
			tek = 0;
			FOR(0, j, (int)pos[i].size())
			{
				//pointer <= j
				while(uk+1 < (int)pos[i-2].size() && pos[i-2][uk+1] <= pos[i][j])
				{
					++uk;
					tek = max(tek, dp[i-2][uk]);
				}
				int temp = upper_bound(all(pos[i-1]), pos[i][j]) - pos[i-1].begin()-1;
				dp[i][j] = max(dp[i][j], (temp>=0?pref[i-1][temp]:0) + tek);
			}
		}
		if(i >= 3)
		{
			tek = 0;
			int uk = (int)pos[i-2].size();
			for(int j = (int)pos[i].size() - 1; j >= 0; --j)
			{
				//pointer > j
				while(uk-1 >= 0 && pos[i-2][uk-1] > pos[i][j])
				{
					uk--;
					int temp = upper_bound(all(pos[i-1]), pos[i-2][uk])-pos[i-1].begin()-1;
					tek = max(tek, dp[i-2][uk] + (temp>=0?pref[i-1][temp]:0));
				}
				dp[i][j] = max(dp[i][j], tek);
			}
		}
		if(i >= 3)
		{
			FOR(0, j, (int)pos[i].size())
			{
				int temp = upper_bound(all(pos[i-1]), pos[i][j])-pos[i-1].begin()-1;
				dp[i][j] = max(dp[i][j], Dp[i-3]+(temp>=0?pref[i-1][temp]:0));
			}
		}
		if(i >= 2)
		{
			tek = -inf;
			int uk = (int)pos[i-1].size();
			for(int j = (int)pos[i].size()-1; j >= 0; --j)
			{
				//pointer > j
				while(uk-1>=0 && pos[i-1][uk-1] > pos[i][j])
				{
					uk--;
					int temp = upper_bound(all(pos[i]), pos[i-1][uk]) - pos[i].begin()-1;
					tek = max(tek, max(dp2[i-1][uk],dp[i-1][uk])+(temp>=0?pref[i][temp]:0));
				}
				dp2[i][j] = max(dp2[i][j], tek - pref[i][j]);
				int temp = upper_bound(all(pos[i+1]), pos[i][j])-pos[i+1].begin()-1;
				Dp[i] = max(Dp[i], dp2[i][j] + (temp>=0?pref[i+1][temp]:0));
			}
		}
		FOR(0, j, pos[i].size())
		{
			int temp = upper_bound(all(pos[i+1]), pos[i][j])-pos[i+1].begin()-1;
			Dp[i] = max(Dp[i], dp[i][j] + (temp>=0?pref[i+1][temp]:0));
		}
		Dp[i] = max(Dp[i-1], Dp[i]);
		ans = max(ans, Dp[i]);
/*		cout << "FOR " << i << endl;
		FOR(0, j, pos[i].size())
			cout << dp[i][j] << " ";
		cout << endl;*/
//		cout << Dp[i] << " " << i << endl;
	}
	return ans;
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  156 |   FOR(0, j, pos[i].size())
      |          ~~~~~~~~~~~~~~~~              
fish.cpp:156:3: note: in expansion of macro 'FOR'
  156 |   FOR(0, j, pos[i].size())
      |   ^~~

• 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