#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int MAX_C= 200;
const int MAX_R = 5000;
const int INF= 1e9;
const int BLOCK_SZ = 100;
const int BLOCK_NB = 100;
struct Step{
vector<vector<int>> tr;
Step(){};
Step(int nbC){
tr.resize(nbC, vector<int> (nbC, INF));
for(int i = 0; i<nbC; i++){
tr[i][i] = 0;
}
}
Step(int nbC, vector<int> lr, vector<int> d){
assert(lr.size() == nbC-1);
assert(d.size() == nbC);
tr.resize(nbC, vector<int> (nbC, 0));
vector<int> prefCost(nbC);
for(int iC = 0; iC<nbC-1; iC++){
prefCost[iC+1] = prefCost[iC] + lr[iC];
}
for(int beginC = 0; beginC<nbC; beginC++){
for(int endC = 0; endC<nbC; endC++){
if(beginC<=endC){
tr[beginC][endC] = prefCost[endC] - prefCost[beginC] + d[endC];
}
else{
tr[beginC][endC] = prefCost[beginC] - prefCost[endC] + d[endC];
}
}
}
}
void display(){
/*for(int i = 0; i<tr.size(); i++){
for(auto e: tr[i]){
cout<<e<<" ";
}
cout<<endl;
}*/
}
};
int nbC;
void mergeBegin(Step &l, Step &r, Step&res, int Begin, int lMid, int rMid, int lEnd, int rEnd){
if(rEnd<lEnd){
return;
}
int splitEnd = (lEnd+rEnd)/2;
int minC= 1e9;
int minMid = (lMid+rMid)/2;
for(int iMid = lMid; iMid<=rMid; iMid++){
if(l.tr[Begin][iMid] + r.tr[iMid][splitEnd] < minC){
minMid= iMid;
minC = l.tr[Begin][iMid] + r.tr[iMid][splitEnd];
}
}
res.tr[Begin][splitEnd] = minC;
mergeBegin(l, r, res, Begin, lMid, minMid, lEnd, splitEnd-1);
mergeBegin(l, r, res, Begin, minMid, rMid, splitEnd+1, rEnd);
}
Step merge(Step& a, Step b){
Step res(nbC);
for(int iBegin = 0; iBegin<nbC; iBegin++){
mergeBegin(a, b, res, iBegin, 0, nbC-1, 0, nbC-1);
}
return res;
}
Step steps[BLOCK_NB];
vector<int> lr[MAX_R], d[MAX_R];
Step total;
int nbR;
void recalc_Big(){
total = Step(nbC);
for(int i = 0; i<=(nbR)/BLOCK_SZ; i++){
//total.display();
steps[i].display();
total = merge(total, steps[i]);
//total.display();
}
}
void recalc_block(int i){
steps[i] = Step(nbC);
for(int iR = i*BLOCK_SZ; iR<min((i+1)*BLOCK_SZ, nbR); iR++){
steps[i] = merge(steps[i], Step(nbC, lr[iR], d[iR]));
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
nbC = C;
nbR = R;
for(int iR = 0; iR<R; iR++){
lr[iR].resize(C-1);
d[iR].resize(C);
for(int i = 0; i<C-1; i++){
lr[iR][i] = H[iR][i];
}
if(iR<R-1){
for(int i = 0; i<C; i++){
d[iR][i] = V[iR][i];
}
}
else{
for(int i = 0; i<C; i++){
d[iR][i] = 0;
}
}
//steps.push_back(Step(C, lr[iR], d[iR]));
//steps.back().display();
}
for(int i = 0; i<=(nbR)/BLOCK_SZ; i++){
recalc_block(i);
}
recalc_Big();
}
void changeH(int P, int Q, int W) {
lr[P][Q] = W;
recalc_block(P/BLOCK_SZ);
recalc_Big();
}
void changeV(int P, int Q, int W) {
d[P][Q] = W;
recalc_block(P/BLOCK_SZ);
recalc_Big();
}
int escape(int V1, int V2) {
return total.tr[V1][V2];
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | int res;
| ^~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from wombats.cpp:2:
wombats.cpp: In constructor 'Step::Step(int, std::vector<int>, std::vector<int>)':
wombats.cpp:24:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
24 | assert(lr.size() == nbC-1);
| ~~~~~~~~~~^~~~~~~~
wombats.cpp:25:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
25 | assert(d.size() == nbC);
| ~~~~~~~~~^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
4956 KB |
Output is correct |
2 |
Correct |
11 ms |
5116 KB |
Output is correct |
3 |
Correct |
49 ms |
6696 KB |
Output is correct |
4 |
Correct |
11 ms |
4952 KB |
Output is correct |
5 |
Correct |
10 ms |
5112 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2652 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
43 ms |
3668 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1358 ms |
3040 KB |
Output is correct |
2 |
Correct |
1276 ms |
2904 KB |
Output is correct |
3 |
Correct |
1366 ms |
2908 KB |
Output is correct |
4 |
Correct |
1361 ms |
3084 KB |
Output is correct |
5 |
Correct |
1367 ms |
2904 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
0 ms |
604 KB |
Output is correct |
9 |
Correct |
6505 ms |
3104 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
8792 KB |
Output is correct |
2 |
Correct |
20 ms |
8792 KB |
Output is correct |
3 |
Correct |
18 ms |
8796 KB |
Output is correct |
4 |
Correct |
39 ms |
9564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1306 ms |
2904 KB |
Output is correct |
2 |
Correct |
1288 ms |
3160 KB |
Output is correct |
3 |
Correct |
1398 ms |
3088 KB |
Output is correct |
4 |
Correct |
1331 ms |
3092 KB |
Output is correct |
5 |
Correct |
1288 ms |
2908 KB |
Output is correct |
6 |
Correct |
17 ms |
8792 KB |
Output is correct |
7 |
Correct |
17 ms |
8796 KB |
Output is correct |
8 |
Correct |
17 ms |
8816 KB |
Output is correct |
9 |
Correct |
39 ms |
9628 KB |
Output is correct |
10 |
Correct |
11 ms |
4952 KB |
Output is correct |
11 |
Correct |
11 ms |
5120 KB |
Output is correct |
12 |
Correct |
52 ms |
6688 KB |
Output is correct |
13 |
Correct |
11 ms |
4956 KB |
Output is correct |
14 |
Correct |
11 ms |
5120 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
2648 KB |
Output is correct |
19 |
Correct |
1 ms |
2648 KB |
Output is correct |
20 |
Correct |
1 ms |
2652 KB |
Output is correct |
21 |
Correct |
1 ms |
2652 KB |
Output is correct |
22 |
Correct |
1 ms |
2652 KB |
Output is correct |
23 |
Correct |
1 ms |
2652 KB |
Output is correct |
24 |
Correct |
1 ms |
2652 KB |
Output is correct |
25 |
Correct |
51 ms |
3668 KB |
Output is correct |
26 |
Correct |
1 ms |
2648 KB |
Output is correct |
27 |
Correct |
6388 ms |
3092 KB |
Output is correct |
28 |
Correct |
10247 ms |
15420 KB |
Output is correct |
29 |
Correct |
9712 ms |
16828 KB |
Output is correct |
30 |
Correct |
9843 ms |
16776 KB |
Output is correct |
31 |
Correct |
10222 ms |
20500 KB |
Output is correct |
32 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1301 ms |
3016 KB |
Output is correct |
2 |
Correct |
1282 ms |
2908 KB |
Output is correct |
3 |
Correct |
1366 ms |
3088 KB |
Output is correct |
4 |
Correct |
1397 ms |
3084 KB |
Output is correct |
5 |
Correct |
1360 ms |
2908 KB |
Output is correct |
6 |
Correct |
18 ms |
8796 KB |
Output is correct |
7 |
Correct |
35 ms |
8792 KB |
Output is correct |
8 |
Correct |
25 ms |
8796 KB |
Output is correct |
9 |
Correct |
52 ms |
9560 KB |
Output is correct |
10 |
Correct |
11 ms |
4696 KB |
Output is correct |
11 |
Correct |
11 ms |
5112 KB |
Output is correct |
12 |
Correct |
51 ms |
6556 KB |
Output is correct |
13 |
Correct |
11 ms |
4952 KB |
Output is correct |
14 |
Correct |
11 ms |
5116 KB |
Output is correct |
15 |
Correct |
3436 ms |
25340 KB |
Output is correct |
16 |
Execution timed out |
20017 ms |
26604 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |