제출 #1247455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247455		lovrot	메기 농장 (IOI22_fish)	C++20	9 / 100	150 ms	33764 KiB

fish

#define db(...) fprintf(stderr, __VA_ARGS__)
#include "fish.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <vector>
#include <queue>

#define X first
#define Y second
#define PB push_back

using namespace std; 

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
const ll OO = 1e18;

struct fish { 
	int x, w, c, i;
	fish() {}
	fish(int x, int w, int c, int i) : x(x), w(w), c(c), i(i) {}
};

int n, m;

vector<ll> dp[N][2];
vector<pii> s[N];

ll max_weights(int nn, int mm, vector<int> xx, vector<int> yy, vector<int> ww) {
	n = nn;
	m = mm;

	for(int i = 0; i < m; ++i) { 
		s[xx[i]].PB({yy[i], ww[i]});
	}

	for(int i = 0; i < n; ++i) { 
		s[i].PB({n, 0});
		sort(s[i].begin(), s[i].end()); 
	}

	ll ans = 0;
	for(int i = n - 1; i >= 0; --i) { 
		vector<fish> f;
		for(int j = 0; j < 2; ++j) { dp[i][j].resize(s[i].size(), 0); }

		for(int j = 0; j < (int) s[i].size(); ++j) { f.PB(fish(s[i][j].X, s[i][j].Y, 0, j)); }
		for(int j = 0; j < (int) s[i + 1].size(); ++j) { f.PB(fish(s[i + 1][j].X, s[i + 1][j].Y, 1, j)); }

		sort(f.begin(), f.end(), [](const fish &a, const fish &b) { 
			return a.x < b.x || (a.x == b.x && a.c > b.c);
		});
		{ ll axi = -OO, prf = 0;
		for(const fish &j : f) { 
			if(j.c == 0) { 
				dp[i][0][j.i] = max(0LL, axi + prf);
			} else { 
				axi = max(axi, dp[i + 1][0][j.i] - prf);
				prf += j.w;
			}
		} }

		sort(f.begin(), f.end(), [](fish a, fish b) { 
			return a.x > b.x || (a.x == b.x && a.c < b.c);
		});
		{ ll axi = -OO, prf = 0;
		for(const fish &j : f) { 
			if(j.c == 0) { 
				prf += j.w;
				dp[i][1][j.i] = max(0LL, axi + prf);
			} else { 
				axi = max(axi, dp[i + 1][1][j.i] - prf);
			}
		} }

		vector<fish> f2;
		for(int j = 0; j < (int) s[i + 1].size(); ++j) { f2.PB(fish(s[i + 1][j].X, s[i + 1][j].Y, 1, j)); }
		for(int j = 0; j < (int) s[i + 2].size(); ++j) { f2.PB(fish(s[i + 2][j].X, s[i + 2][j].Y, 2, j)); }
		sort(f2.begin(), f2.end(), [](const fish &a, const fish &b) { 
				return a.x < b.x || (a.x == b.x && a.c > b.c);
		});

		ll axi0 = -OO, axi1 = -OO, prf = 0;
		for(const fish &j : f2) { 
			if(j.c == 1) { prf += j.w; }
			else { 
				axi0 = max(axi0, dp[i + 2][1][j.i]);
				axi1 = max(axi1, dp[i + 2][1][j.i] + prf);
			}
		}

		sort(f.begin(), f.end(), [](const fish &a, const fish &b) { 
				return a.x < b.x || (a.x == b.x && a.c < b.c); 
		});
			
		prf = 0;
		for(const fish &j : f) { 
			if(j.c == 1) { prf += j.w; }
			else { 
				dp[i][0][j.i] = max(dp[i][0][j.i], max(prf + axi0, axi1));
				dp[i][1][j.i] = max(dp[i][0][j.i], dp[i][1][j.i]);

				ans = max(ans, dp[i][1][j.i]);
			}
		}

//		db("%d: ", i);
//		for(int j = 0; j < (int) s[i].size(); ++j) { db("(%d %lld %lld) ", s[i][j].X, dp[i][0][j], dp[i][1][j]); }
//		db("\n");
	}
	return ans; 
}

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