QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#120616 | #1154. Wombats | Qwerty1232# | 0 | 513ms | 14776kb | C++17 | 3.8kb | 2023-07-07 01:20:44 | 2024-05-26 02:55:57 |
Judging History
answer
#include "wombats.h"
#include <bits/stdc++.h>
constexpr int inf = 1e9 + 1;
int n, m;
struct Cum {
std::vector<int> L;
std::vector<std::vector<int>> data;
std::vector<std::vector<int>> v, h;
int len;
Cum() {
len = 0;
}
Cum(std::vector<int> v, std::vector<int> h) {
assert(v.size() == m);
assert(h.size() == m - 1);
len = 1;
L = v;
this->v.push_back(v);
this->h.push_back(h);
return;
std::vector<int> ph(m);
std::partial_sum(h.begin(), h.end(), ph.begin() + 1);
data.assign(m, std::vector<int>(m));
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
data[i][j] = abs(ph[i] - ph[j]);
}
}
}
};
Cum fuck(Cum a) {
if (a.len == -1) {
return a;
}
int l = a.len;
Cum res;
res.len = -1;
res.data.resize(m);
res.L = a.L;
for (int i = 0; i < m; i++) {
std::vector<int> dp(m, inf);
dp[i] = 0;
auto shit = [&](auto& h) {
for (int j = 1; j < m; j++) {
dp[j] = std::min(dp[j], dp[j - 1] + h[j - 1]);
}
for (int j = m - 2; j >= 0; j--) {
dp[j] = std::min(dp[j], dp[j + 1] + h[j]);
}
};
shit(a.h[0]);
for (int j = 1; j < l; j++) {
for (int t = 0; t < m; t++) {
dp[t] += a.v[j][t];
}
shit(a.h[j]);
}
res.data[i] = dp;
}
return res;
}
Cum merge(Cum a, Cum b) {
if (!a.len || !b.len) {
return a.len ? a : b;
}
if (a.len == -1 || b.len == -1) {
if (a.len != -1) {
a = fuck(a);
}
if (b.len != -1) {
b = fuck(b);
}
} else {
a.L = b.L;
a.len += b.len;
a.v.insert(a.v.end(), b.v.begin(), b.v.end());
a.h.insert(a.h.end(), b.h.begin(), b.h.end());
if (a.len > 0) {
a = fuck(a);
}
return a;
}
Cum res;
res.len = -1;
res.L = a.L;
res.data.assign(m, std::vector<int>(m, inf));
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
for (int t = 0; t < m; t++) {
res.data[i][t] = std::min(res.data[i][t], a.data[i][j] + b.L[j] + b.data[j][t]);
}
}
}
return res;
}
std::vector<std::vector<int>> h, v;
int size;
std::vector<Cum> data;
void build() {
for (size = 1; size < n; size *= 2)
;
data.resize(2 * size);
for (int i = 0; i < n; i++) {
data[size + i] = Cum(v[i], h[i]);
}
for (int i = size - 1; i > 0; i--) {
data[i] = merge(data[2 * i], data[2 * i + 1]);
}
}
void update(int i) {
data[i + size] = Cum(v[i], h[i]);
i += size;
for (i >>= 1; i > 0; i >>= 1) {
data[i] = merge(data[2 * i], data[2 * i + 1]);
}
}
void init(int r, int c, int H[5000][200], int V[5000][200]) {
n = r;
m = c;
h.assign(n, std::vector<int>(m - 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
h[i][j] = H[i][j];
}
}
v.assign(n, std::vector<int>(m));
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
v[i + 1][j] = V[i][j];
}
}
build();
}
void changeH(int p, int q, int w) {
h[p][q] = w;
update(p);
}
void changeV(int p, int q, int w) {
v[p + 1][q] = w;
update(p + 1);
}
int escape(int v1, int v2) {
if (data[1].len != -1) {
data[1] = fuck(data[1]);
}
int res = data[1].data[v1][v2];
return res;
// return 42;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 9
Accepted
time: 3ms
memory: 11216kb
input:
5000 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 500 lines
Test #2:
score: -9
Wrong Answer
time: 3ms
memory: 10420kb
input:
4999 1 447 741 689 474 539 506 732 156 94 221 858 311 318 930 146 187 13 881 960 441 480 653 504 999 274 251 772 626 944 822 314 881 695 235 952 241 204 347 821 392 641 146 316 410 305 658 977 748 363 387 550 611 991 287 105 927 679 460 660 952 310 680 669 697 768 30 25 979 743 20 624 174 877 928 46...
output:
2517633 2517633 2517783 2517783 2517783 2517783 2518327 2519367 2519367 2518623 2518623 2518635 2518635 2518635 2518671 2518333 2518521 2517343 2517343 2516891 2516891 2518399 2518399 2518121 2518121 2518121 2517711 2518419 2518051 2518051 2518051 2518051 2518413 2518969 2518583 2518583 2518583 2519...
result:
wrong answer 1st lines differ - expected: '2499534', found: '2517633'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 1ms
memory: 5880kb
input:
20 20 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 ...
output:
1 1 3 2 2 0 2 3 2 1 2 2 3 2 2 2 1 1 3 2 3 1 1 1 0 4 0 1 3 1 1 1 1 2 3 1 1 4 0 1 2 1 2 1 1 2 2 0 2 2 1 2 3 2 2 1 2 1 1 3 3 0 0 2 1 2 2 5 1 2 0 0 4 4 2 1 2 2 1 2 2 1 2 0 0 1 1 2 2 3 1 2 1 1 4 2 1 0 2 1 3 1 1 0 1 3 2 1 1 1 0 1 2 2 2 2 1 2 1 1 1 3 1 1 2 0 2 1 2 2 1 2 3 2 1 1 1 3 3 1 3 0 0 3 1 3 4 1 1 2 ...
result:
wrong answer 1st lines differ - expected: '2', found: '1'
Subtask #3:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 513ms
memory: 10812kb
input:
99 100 278 927 579 441 245 179 75 110 797 424 854 825 213 194 8 666 556 81 205 126 225 882 913 85 319 94 784 83 486 391 262 251 623 746 706 453 842 242 414 876 885 88 175 334 971 539 90 860 11 32 402 776 314 301 966 800 744 20 777 681 535 55 191 1 773 503 55 223 285 3 136 505 644 175 686 454 2 818 3...
output:
24854 26323 31410 28597 34651 25173 30998 29528 29479 30436 26264 27994 28144 26380 28096 29519 28035 28912 33832 26534 34475 40963 26029 31290 29570 36335 25464 26288 27469 30714 34614 30720 31047 27456 31245 42217 27185 29345 27641 30145 27501 36467 27125 30330 29165 27198 31924 33389 30011 27324 ...
result:
wrong answer 1st lines differ - expected: '34137', found: '24854'
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 3ms
memory: 14776kb
input:
4999 2 57 194 293 623 704 290 534 103 734 55 774 398 571 972 268 57 567 207 425 914 855 650 38 540 496 242 353 263 889 192 216 416 414 54 80 451 456 956 809 169 909 394 244 936 77 180 653 263 338 732 752 739 250 759 738 450 431 243 50 897 790 606 389 146 148 878 611 707 802 623 187 98 653 244 127 75...
output:
1994772 1994755 1994715 1994812 1994772 1994755 1993502 1993405 1993445 1993462 1993395 1993492 1993395 1993492 1993702 1993605 1993605 1993702 1993605 1993702 1993645 1993662 1993605 1993702 1993605 1993702 1993605 1993702 1993662 1993645 1993702 1993605 1993605 1993702 1993630 1993533 1993590 1993...
result:
wrong answer 1st lines differ - expected: '2116460', found: '1994772'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%