oj.uz

답안 #1093241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1093241 2024-09-26T10:42:19 Z Wansur 웜뱃 (IOI13_wombats) C++17
76 / 100
 20000 ms 44840 KB 
#include <bits/stdc++.h>
#include "wombats.h"
#define ent '\n'

using namespace std;
typedef long long ll;

struct asd{
    int l, r, t[202][202];
    asd(){
        l = r = 0;
        for(int i=0;i<202;i++){
            for(int j=0;j<202;j++){
                t[i][j] = 1e9;
            }
        }
    }
};

int h[5050][205], v[5050][205];
int dp[5050][205];
int n, m, k, N;

asd merge(asd a, asd b){
    asd ans;
    ans.l = a.l, ans.r = b.r;
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){
                ans.t[i][k] = min(ans.t[i][k], a.t[i][j] + b.t[j][k] + v[a.r][j]); 
            }
        }
    }
    return ans;
}

asd calc(int l, int r){
    asd ans;
    ans.l = l, ans.r = r;
    for(int x=0;x<m;x++){
        for(int i=l;i<=r;i++){
            for(int j=0;j<m;j++)
                dp[i][j] = 1e9;
        }
        dp[l][x] = 0;
        for(int i=l;i<r;i++){
            for(int j=m-2;j>=0;j--){
                dp[i][j] = min(dp[i][j], dp[i][j+1] + h[i][j]);
            }
            for(int j=1;j<m;j++){
                dp[i][j] = min(dp[i][j], dp[i][j-1] + h[i][j-1]);
            }
            for(int j=0;j<m;j++){
                dp[i+1][j] = dp[i][j] + v[i][j];
            }
        }
        for(int j=m-2;j>=0;j--){
            dp[r][j] = min(dp[r][j], dp[r][j+1] + h[r][j]);
        }
        for(int j=1;j<m;j++){
            dp[r][j] = min(dp[r][j], dp[r][j-1] + h[r][j-1]);
        }
        for(int y=0;y<m;y++){
            ans.t[x][y] = dp[r][y];
        }
    }
    return ans;
}

asd t[80], a[20];

void build(int v, int tl, int tr){
    if(tl == tr){
        t[v] = a[tl];
    }
    else{
        int mid = tl + tr >> 1;
        build(v*2, tl, mid);
        build(v*2+1, mid+1, tr);
        t[v] = merge(t[v*2], t[v*2+1]);
    }
}

void upd(int v, int tl , int tr, int pos){
    if(tl == tr){
        t[v] = a[pos];
    }
    else{
        int mid = tl + tr >> 1;
        if(pos <= mid){
            upd(v*2, tl, mid, pos);
        }
        else{
            upd(v*2+1, mid+1, tr, pos);
        }
        t[v] = merge(t[v*2], t[v*2+1]);
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]){
    n = R, m = C;
    for(int i=0;i<n;i++){
        for(int j=0;j<m-1;j++){
            h[i][j] = H[i][j];
        }
    }
    for(int i=0;i<n-1;i++){
        for(int j=0;j<m;j++){
            v[i][j] = V[i][j];
        }
    }
    k = 313;
    for(int i=0;i<n;i+=k){
        int j = min(i + k - 1, n - 1);
        a[i / k] = calc(i, j);
        N = i / k;
    }
    build(1, 0 , N);
}

void changeH(int i, int j, int x){
    h[i][j] = x;
    a[i / k] = calc(i / k * k, min(n, (i + k) / k * k) - 1);
    upd(1, 0, N, i / k);
}

void changeV(int i, int j, int x){
    v[i][j] = x;
    a[i / k] = calc(i / k * k, min(n, (i + k) / k * k) - 1);
    upd(1, 0, N, i / k);
}

int escape(int v, int u){
    return t[1].t[v][u];
}

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;
      |      ^~~
wombats.cpp: In function 'void build(int, int, int)':
wombats.cpp:77:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~
wombats.cpp: In function 'void upd(int, int, int, int)':
wombats.cpp:89:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 29276 KB Output is correct
2 Correct 92 ms 29272 KB Output is correct
3 Correct 125 ms 32084 KB Output is correct
4 Correct 85 ms 29276 KB Output is correct
5 Correct 89 ms 29272 KB Output is correct
6 Correct 7 ms 16476 KB Output is correct
7 Correct 9 ms 16476 KB Output is correct
8 Correct 9 ms 16476 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16472 KB Output is correct
2 Correct 6 ms 16476 KB Output is correct
3 Correct 6 ms 16476 KB Output is correct
4 Correct 6 ms 16476 KB Output is correct
5 Correct 6 ms 16600 KB Output is correct
6 Correct 7 ms 16472 KB Output is correct
7 Correct 7 ms 16476 KB Output is correct
8 Correct 6 ms 16500 KB Output is correct
9 Correct 7 ms 16472 KB Output is correct
10 Correct 6 ms 16684 KB Output is correct
11 Correct 45 ms 19028 KB Output is correct
12 Correct 7 ms 16472 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 711 ms 17048 KB Output is correct
2 Correct 677 ms 16988 KB Output is correct
3 Correct 714 ms 16984 KB Output is correct
4 Correct 707 ms 16988 KB Output is correct
5 Correct 677 ms 16988 KB Output is correct
6 Correct 8 ms 16476 KB Output is correct
7 Correct 7 ms 16492 KB Output is correct
8 Correct 7 ms 16500 KB Output is correct
9 Correct 3454 ms 17072 KB Output is correct
10 Correct 8 ms 16472 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 37212 KB Output is correct
2 Correct 90 ms 37212 KB Output is correct
3 Correct 91 ms 37212 KB Output is correct
4 Correct 111 ms 38480 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 701 ms 17044 KB Output is correct
2 Correct 673 ms 17036 KB Output is correct
3 Correct 717 ms 16984 KB Output is correct
4 Correct 717 ms 16984 KB Output is correct
5 Correct 671 ms 16988 KB Output is correct
6 Correct 92 ms 37212 KB Output is correct
7 Correct 96 ms 37208 KB Output is correct
8 Correct 92 ms 37308 KB Output is correct
9 Correct 112 ms 38480 KB Output is correct
10 Correct 83 ms 29276 KB Output is correct
11 Correct 84 ms 29320 KB Output is correct
12 Correct 136 ms 32084 KB Output is correct
13 Correct 85 ms 29324 KB Output is correct
14 Correct 84 ms 29272 KB Output is correct
15 Correct 7 ms 16476 KB Output is correct
16 Correct 7 ms 16488 KB Output is correct
17 Correct 7 ms 16392 KB Output is correct
18 Correct 7 ms 16476 KB Output is correct
19 Correct 8 ms 16452 KB Output is correct
20 Correct 7 ms 16476 KB Output is correct
21 Correct 6 ms 16476 KB Output is correct
22 Correct 7 ms 16476 KB Output is correct
23 Correct 7 ms 16472 KB Output is correct
24 Correct 7 ms 16476 KB Output is correct
25 Correct 46 ms 18840 KB Output is correct
26 Correct 6 ms 16476 KB Output is correct
27 Correct 3481 ms 17072 KB Output is correct
28 Correct 12809 ms 41044 KB Output is correct
29 Correct 12913 ms 37416 KB Output is correct
30 Correct 12568 ms 37284 KB Output is correct
31 Correct 12995 ms 42960 KB Output is correct
32 Correct 7 ms 16476 KB Output is correct

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 708 ms 16988 KB Output is correct
2 Correct 661 ms 17040 KB Output is correct
3 Correct 701 ms 16984 KB Output is correct
4 Correct 706 ms 16988 KB Output is correct
5 Correct 676 ms 16984 KB Output is correct
6 Correct 90 ms 37208 KB Output is correct
7 Correct 91 ms 37248 KB Output is correct
8 Correct 97 ms 37212 KB Output is correct
9 Correct 117 ms 38484 KB Output is correct
10 Correct 83 ms 29316 KB Output is correct
11 Correct 86 ms 29272 KB Output is correct
12 Correct 122 ms 31984 KB Output is correct
13 Correct 86 ms 29276 KB Output is correct
14 Correct 82 ms 29272 KB Output is correct
15 Correct 2013 ms 44840 KB Output is correct
16 Execution timed out 20009 ms 42252 KB Time limit exceeded
17 Halted 0 ms 0 KB -