This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int r, c;
vector< vector<int> > h, v;
vector<int> range;
vector< vector<int> > calc(int x) {
vector< vector<int> > ans(c, vector<int>(c, INF)), pre(2, vector<int>(c, 0));
for (int i = 0; i < 2; i++) for (int j = 1; j < c; j++) pre[i][j] = pre[i][j - 1] + h[x + i][j - 1];
for (int i = 0; i < c; i++) {
int mx = -INF;
for (int j = 0; j < c; j++) {
mx = max(mx, pre[1][j] - abs(pre[0][i] - pre[0][j]) - v[x][j]);
ans[i][j] = min(ans[i][j], pre[1][j] - mx);
}
int mn = INF;
for (int j = c - 1; j >= 0; j--) {
mn = min(mn, abs(pre[0][i] - pre[0][j]) + v[x][j] + pre[1][j]);
ans[i][j] = min(ans[i][j], mn - pre[1][j]);
}
}
return move(ans);
}
vector< vector<int> > combine(const vector< vector<int> > &a, const vector< vector<int> > &b) {
vector< vector<int> > ans(c, vector<int>(c, INF)), best(c, vector<int>(c, -1));
for (int i = 0; i < c; i++) {
for (int j = c - 1; j >= 0; j--) {
int l = i == 0 ? 0 : best[i - 1][j], r = j == c - 1 ? c - 1 : best[i][j + 1];
for (int k = l; k <= r; k++) {
if (a[i][k] + b[k][j] < ans[i][j]) {
ans[i][j] = a[i][k] + b[k][j];
best[i][j] = k;
}
}
}
}
return move(ans);
}
vector< vector<int> > calc(int l, int r) {
vector< vector<int> > ans = calc(l);
for (int i = l + 1; i < r; i++) ans = combine(ans, calc(i));
return move(ans);
}
struct node {
int l, r;
vector< vector<int> > cost;
node *left, *right;
} *root;
node *build(int l, int r) {
if (l + 10 >= r) {
for (int i = l; i < r; i++) range[i] = l;
return new node{l, r, calc(l, r), nullptr, nullptr};
}
node *left = build(l, (l + r) / 2), *right = build((l + r) / 2, r);
return new node{l, r, combine(left->cost, right->cost), left, right};
}
void update(node *cur, int x) {
if (cur->left == nullptr) {
assert(cur->l == x);
cur->cost = calc(cur->l, cur->r);
return;
}
if (cur->right->l <= x) update(cur->right, x);
else update(cur->left, x);
cur->cost = combine(cur->left->cost, cur->right->cost);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R, c = C;
h.assign(r, vector<int>(c - 1));
for (int i = 0; i < r; i++) for (int j = 0; j < c - 1; j++) h[i][j] = H[i][j];
v.assign(r - 1, vector<int>(c));
for (int i = 0; i < r - 1; i++) for (int j = 0; j < c; j++) v[i][j] = V[i][j];
range.resize(r - 1);
root = build(0, r - 1);
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
if (P > 0) update(root, range[P - 1]);
if (P < r - 1) update(root, range[P]);
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
update(root, range[P]);
}
int escape(int V1, int V2) {
return root->cost[V1][V2];
}
Compilation message (stderr)
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | int res;
| ^~~
wombats.cpp: In function 'std::vector<std::vector<int> > calc(int)':
wombats.cpp:26:14: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
26 | return move(ans);
| ~~~~^~~~~
wombats.cpp:26:14: note: remove 'std::move' call
wombats.cpp: In function 'std::vector<std::vector<int> > combine(const std::vector<std::vector<int> >&, const std::vector<std::vector<int> >&)':
wombats.cpp:42:14: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
42 | return move(ans);
| ~~~~^~~~~
wombats.cpp:42:14: note: remove 'std::move' call
wombats.cpp: In function 'std::vector<std::vector<int> > calc(int, int)':
wombats.cpp:48:14: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
48 | return move(ans);
| ~~~~^~~~~
wombats.cpp:48:14: note: remove 'std::move' call
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |