oj.uz

답안 #1007788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1007788 2024-06-25T13:25:07 Z bachhoangxuan 웜뱃 (IOI13_wombats) C++17
76 / 100
 20000 ms 192340 KB 
#pragma GCC optimize("O3")
#pragma GCC target("arch=haswell")

#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3+5;
const int maxm = 2e2+5;
const int B = 10;
const int maxs = 1030;
const int inf = 1e9;

int R,C,S;
int H[maxn][maxm],V[maxn][maxm];
int tree[maxs][maxm][maxm];

void init(int x,int id){
    int l=x*B,r=min((x+1)*B,R);
    for(int i=0;i<C;i++) for(int j=0;j<C;j++) tree[id][i][j]=(i!=j)*inf;
    for(int t=l;t<r;t++){
        for(int i=0;i<C;i++){
            for(int j=1;j<C;j++) tree[id][i][j]=min(tree[id][i][j],tree[id][i][j-1]+H[t][j-1]);
            for(int j=C-1;j>0;j--) tree[id][i][j-1]=min(tree[id][i][j-1],tree[id][i][j]+H[t][j-1]);
            for(int j=0;j<C;j++) tree[id][i][j]+=V[t][j];
        }
    }
}
void merge(int id){
    for(int i=0;i<C;i++) for(int j=0;j<C;j++){
        tree[id][i][j]=inf;
        for(int k=0;k<C;k++) tree[id][i][j]=min(tree[id][i][j],tree[id<<1][i][k]+tree[id<<1|1][k][j]);
    }
}

void build(int l,int r,int id){
    if(l==r) return init(l,id);
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    merge(id);
}
void update(int l,int r,int id,int p){
    if(l==r) return init(l,id);
    int mid=(l+r)>>1;
    if(p<=mid) update(l,mid,id<<1,p);
    else update(mid+1,r,id<<1|1,p);
    merge(id);
}

void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
    R=_R;C=_C;
    for(int i=0;i<R;i++) for(int j=0;j<C-1;j++) H[i][j]=_H[i][j];
    for(int i=0;i<R-1;i++) for(int j=0;j<C;j++) V[i][j]=_V[i][j];
    S=(R-1)/B;
    build(0,S,1);
}

void changeH(int P, int Q, int W) {
    H[P][Q]=W;
    update(0,S,1,P/B);
}

void changeV(int P, int Q, int W) {
    V[P][Q]=W;
    update(0,S,1,P/B);
}

int escape(int V1, int V2) {
    return tree[1][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;
      |      ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 95068 KB Output is correct
2 Correct 8 ms 91108 KB Output is correct
3 Correct 47 ms 95964 KB Output is correct
4 Correct 9 ms 93020 KB Output is correct
5 Correct 9 ms 92952 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 44 ms 10840 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 326 ms 13136 KB Output is correct
2 Correct 406 ms 12892 KB Output is correct
3 Correct 344 ms 12888 KB Output is correct
4 Correct 356 ms 12892 KB Output is correct
5 Correct 386 ms 12892 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1797 ms 12888 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 98248 KB Output is correct
2 Correct 10 ms 94188 KB Output is correct
3 Correct 9 ms 96212 KB Output is correct
4 Correct 29 ms 95576 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 337 ms 12888 KB Output is correct
2 Correct 404 ms 12888 KB Output is correct
3 Correct 367 ms 12896 KB Output is correct
4 Correct 354 ms 12892 KB Output is correct
5 Correct 372 ms 12912 KB Output is correct
6 Correct 10 ms 98136 KB Output is correct
7 Correct 11 ms 99932 KB Output is correct
8 Correct 12 ms 97964 KB Output is correct
9 Correct 30 ms 101460 KB Output is correct
10 Correct 9 ms 99164 KB Output is correct
11 Correct 9 ms 99148 KB Output is correct
12 Correct 47 ms 101808 KB Output is correct
13 Correct 11 ms 97116 KB Output is correct
14 Correct 10 ms 96992 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 1 ms 8536 KB Output is correct
25 Correct 39 ms 10888 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 1800 ms 12904 KB Output is correct
28 Correct 4691 ms 143080 KB Output is correct
29 Correct 4328 ms 133204 KB Output is correct
30 Correct 4330 ms 131608 KB Output is correct
31 Correct 4557 ms 144724 KB Output is correct
32 Correct 1 ms 8540 KB Output is correct

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 12896 KB Output is correct
2 Correct 364 ms 12892 KB Output is correct
3 Correct 368 ms 13136 KB Output is correct
4 Correct 330 ms 12892 KB Output is correct
5 Correct 378 ms 12812 KB Output is correct
6 Correct 11 ms 98140 KB Output is correct
7 Correct 11 ms 100188 KB Output is correct
8 Correct 11 ms 98140 KB Output is correct
9 Correct 32 ms 101428 KB Output is correct
10 Correct 9 ms 97112 KB Output is correct
11 Correct 10 ms 99204 KB Output is correct
12 Correct 47 ms 101716 KB Output is correct
13 Correct 11 ms 97112 KB Output is correct
14 Correct 10 ms 99112 KB Output is correct
15 Correct 4187 ms 192340 KB Output is correct
16 Execution timed out 20066 ms 192188 KB Time limit exceeded
17 Halted 0 ms 0 KB -