| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 723005 | mathematik | 메기 농장 (IOI22_fish) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define m 1000000
#define ll long long
using namespace std;
vector<pair<ll, ll>> best(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> fish) {
steg.push_back({m + 1, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> erg;
ll ind = 0, sum = 0;
for (ll i = 0; i < fish.size(); i++)
{
while (steg[ind + 1].first <= fish[i].first)
ind++;
erg.push_back({fish[i].first, steg[ind].second + sum});
sum += fish[i].second;
}
return erg;
}
vector<pair<ll, ll>> collect(vector<pair<ll, ll>> scores, vector<pair<ll, ll>> fish) {
scores.push_back({m, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> next;
ll ind = 0;
for (ll j = 0; j < fish.size(); j++)
{
while(scores[ind + 1].first < fish[j].first)
ind++;
next.push_back({fish[j].first - 1, scores[ind].second});
}
return next;
}
vector<pair<ll, ll>> dp2(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> fish) {
steg.push_back({m, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> scores;
ll score = 0, score_steg = 0;
ll ind = 0, ind_steg = 0;
ll h;
while (ind > 0 | ind_steg > 0) {
if (fish[ind].first < steg[ind_steg].first) {
score += fish[ind].second;
h = fish[ind++].first;
} else {
score_steg = steg[ind_steg].second;
h = steg[ind_steg++].first;
}
if (score_steg > score)
score = score_steg;
scores.push_back({h, score});
}
return scores;
}
vector<pair<ll, ll>> dp(vector<pair<ll, ll>> steg, vector<pair<ll, ll>> fish) {
steg.push_back({m, 0});
fish.push_back({m, 0});
vector<pair<ll, ll>> scores;
ll score = 0, score_steg = 0;
ll ind = fish.size() - 1, ind_steg = steg.size() - 1;
ll h;
while (ind + ind_steg < fish.size() + steg.size() - 2) {
if (fish[ind].first > steg[ind_steg].first) {
score += fish[ind].second;
h = fish[ind--].first;
} else {
score_steg = steg[ind_steg].second;
h = steg[ind_steg--].first;
}
if (score_steg > score)
score = score_steg;
scores.push_back({h, score});
}
return scores;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<pair<ll, ll>>> vert(N);
for (ll i = 0; i < M; i++)
{
vert[X[i]].push_back({Y[i], W[i]});
}
for (ll i = 0; i < N; i++)
{
vert[i].push_back({0, 0});
sort(vert[i].begin(), vert[i].end());
}
vector<pair<ll, ll>> up, down;
for (auto a: vert[0]) {
up.push_back({a.first - 1, 0});
down.push_back({a.first - 1, 0});
}
for (ll i = 0; i < N - 1; i++)
{
vector<pair<ll, ll>> next_up = collect(dp(up, vert[i]), vert[i + 1]);
vector<pair<ll, ll>> next_down = collect(dp2(down, vert[i + 1]), vert[i + 1]);
for (ll j = 0; j < next_down.size(); j++)
{
next_down[j].second = max(next_down[j].second, next_up[j].second);
}
vector<pair<ll, ll>> best_zero = best(down, vert[i + 1]);
for (ll j = 0; j < best_zero.size(); j++)
{
next_up[j].second = max(next_up[j].second, best_zero[j].second);
}
up = next_up;
down = next_down;
assert(up.size() == down.size());
for (int i = 0; i < up.size(); i++)
{
assert(up[i].first == down[i].first);
}
return max(down.front().second, up.back().second);
}