| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 829224 | otarius | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "fish.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long
// #define int long long
// #define int unsigned long long
const ll inf = 1e18 + 7;
const ll weirdMod = 998244353;
int n, m, y, w;
struct segtree {
ll t[400040];
void init(int v = 1, int tl = 1, int tr = n) {
t[v] = -inf;
if (tl == tr)
return;
int tm = (tl + tr) / 2;
init(2 * v, tl, tm);
init(2 * v + 1, tm + 1, tr);
}
void update(int v, int tl, int tr, int pos, int val) {
if (tl == tr) {
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm)
update(2 * v, tl, tm, pos, val);
else update(2 * v + 1, tm + 1, tr, pos, val);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
ll get(int v, int tl, int tr, int l, int r) {
if (l > r)
return -inf;
if (tl == l && tr == r)
return t[v];
int tm = (tl + tr) / 2;
return max(get(2 * v, tl, tm, l, min(r, tm)) +
get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
} t1, t2;
vector<pll> pos[100005];
vector<ll> dp1[100005];
vector<ll> dp2[100005];
ll max_weights(int N, int M, int[] X, int[] Y, int[] W) {
n = N; m = M;
for (int i = 0; i < m; i++) {
X[i]++; Y[i]++;
pos[X[i]].pb({Y[i], W[i]});
}
for (int i = 0; i <= n + 1; i++) {
sort(pos[i].begin(), pos[i].end());
if (pos[i].empty() || pos[i][0].ff != 1) pos[i].pb({1, 0});
if (pos[i].back().ff != n) pos[i].pb({n, 0});
sort(pos[i].begin(), pos[i].end());
dp1[i] = vector<ll>(pos[i].size(), -inf);
dp2[i] = vector<ll>(pos[i].size(), -inf);
}
t1.init(); t2.init();
dp1[0][dp1[0].size() - 1] = 0; dp2[0][0] = 0;
ll a = -inf, b = -inf, ans = 0;
for (int i = 0; i <= n + 1; i++) {
int k = pos[i].size();
if (i >= 1) a = max(a, dp2[i - 1][0]);
if (i >= 2) b = max(b, dp1[i - 2].back());
dp1[i][0] = max(dp1[i][0], a + pos[i][0].sc);
if (i >= 2) dp[i][0] = max(dp1[i][0], dp1[i - 2][0] + pos[i][0].sc);
dp2[i][k - 1] = max(dp2[i][k - 1], b + pos[i][k - 1].sc);
for (int j = 0; j < t; j++) {
y = pos[i][j].ff;
w = pos[i][j].sc;
dp1[i][j] = max(dp1[i][j], t1.get(1, 1, n, 1, y - 1) + w);
t1.update(1, 1, n, y, dp1[i][j]);
}
for (int j = t - 1; j >= 0; j--) {
y = pos[i][j].ff;
w = pos[i][j].sc;
dp2[i][j] = max(dp2[i][j], t2.get(1, 1, n, y + 1, n) + w);
t2.update(1, 1, n, y, dp2[i][j]);
}
ans = max(ans, dp2[i][0]);
}
cout << ans;
}