제출 #637436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637436		blue	메기 농장 (IOI22_fish)	C++17	37 / 100	1092 ms	39368 KiB

fish

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

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vi = vector<int>;
using vvi = vector<vi>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())

void selfmax(ll& a, ll b)
{
	a = max(a, b);
}

ll max_weights(int N, int M, vi X, vi Y, vi W)
{
	for(int j = 0; j < M; j++)
	{
		X[j]++;
		Y[j]++;
	}

	vpll fish[1+N];
	vll fishpref[1+N];

	for(int j = 0; j < M; j++)
	{
		fish[X[j]].push_back({Y[j], W[j]});
	}

	for(int r = 1; r <= N; r++)
	{
		fish[r].push_back({N+1, 0});
		sort(fish[r].begin(), fish[r].end());

		if(fish[r][0].first != 1)
		{
			fish[r].insert(fish[r].begin(), {1, 0});
		}

		fishpref[r] = vll(sz(fish[r]));
		for(int i = 0; i < sz(fishpref[r]); i++)
		{
			fishpref[r][i] = (i == 0 ? 0 : fishpref[r][i-1]) + fish[r][i].second;
		}
	}

	fish[0] = vpll{{0, 0}};
	fishpref[0] = vll{0};

	vvll inc(1+N), dec(1+N);
	inc[0] = dec[0] = vll{0};

	// cerr << "done\n";

	for(int r = 1; r <= N; r++)
	{
		inc[r] = dec[r] = vll(sz(fish[r]), 0);
		for(int i = 0; i < sz(fish[r]); i++)
		{
			// cerr << "\n\n";
			// cerr << r << " : " << i << " " << fish[r][i].first << '\n';

			ll basic = 0;
			if(r >= 2) //leave two columns blank.
			{
				ll thiscatch = 0;
				for(int j = 0; j < sz(fish[r-1]); j++)
					if(fish[r-1][j].first <= fish[r][i].first - 1)
						thiscatch += fish[r-1][j].second;
				selfmax(basic, max(inc[r-2][0], dec[r-2][0]) + thiscatch);

			}

			// cerr << "hello\n";

			//leave one column blank
			if(r >= 2)
			{
				for(int j = 0; j < sz(fish[r-2]); j++)
				{
					// cerr << "j = " << j << " out of (exc) " << sz(fish[r-2]) << '\n';
					ll medcatch = 0;
					for(int k = 0; k < sz(fish[r-1]); k++)
						if(fish[r-1][k].first <= max(fish[r-2][j].first - 1, fish[r][i].first - 1))
							medcatch += fish[r-1][k].second;

					selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + medcatch);
				}
			}

			selfmax(inc[r][i], basic);
			selfmax(dec[r][i], basic);
			

			// cerr << "oneblank done\n";
			// cerr << r << ' ' << fish[r][i].first-1 << " : " << inc[r][i] << ' ' << dec[r][i] << '\n';		}
	// cerr << r << ' ' << fish[r][i].first-1 << " : " << inc[r][i] << ' ' << dec[r][i] << '\n';		
		// cerr << r << ' ' << fish[r][i].first-1 << " : " << inc[r][i] << ' ' << dec[r][i] << '\n';		
		

			for(int j = 0; j < sz(fish[r-1]); j++)
			{
				// cerr << "j = " << j << " , " << fish[r-1][j].first-1 << '\n';
				ll ext = 0;
				if(fish[r-1][j].first - 1 <= fish[r][i].first - 1)
				{
					// cerr << "case 1\n";
					for(int k = j; k < sz(fish[r-1]); k++)
					{
						if(fish[r-1][k].first <= fish[r][i].first - 1)
							ext += fish[r-1][k].second;
					}

					selfmax(inc[r][i], inc[r-1][j] + ext);
					selfmax(dec[r][i], inc[r-1][j] + ext);
				}
				else
				{
					// cerr << "case 2\n";
					for(int k = i; k < sz(fish[r]); k++)
					{
						if(fish[r][k].first <= fish[r-1][j].first - 1)
							ext += fish[r][k].second;
					}

					selfmax(dec[r][i], dec[r-1][j] + ext);
				}
				// cerr << r << ' ' << fish[r][i].first-1 << " : " << inc[r][i] << ' ' << dec[r][i] << '\n';		
		
			}

		}
	}

	ll res = 0;
	for(vll x : inc)
		for(ll y : x)
			res = max(res, y);
	for(vll x : dec)
		for(ll y : x)
			res = max(res, y);

	return res;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 14 / 14
• Subtask 8: 0 / 16