oj.uz

Submission #1093249

# Submission time Handle Problem Language Result Execution time Memory
1093249 2024-09-26T10:58:04 Z Wansur Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 165020 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[701], a[140];

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);
        if(v != 1) 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);
        }
        if(v != 1) 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 = 45;
    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 vv, int u){
    if(N == 0) return a[0].t[vv][u];
    int ans = 1e9;
    for(int i=0;i<m;i++){
        ans = min(ans, t[2].t[vv][i] + t[3].t[i][u] + v[t[2].r][i]);
    }
    return ans;
}

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

# Verdict Execution time Memory Grader output
1 Correct 164 ms 148108 KB Output is correct
2 Correct 157 ms 148048 KB Output is correct
3 Correct 192 ms 149584 KB Output is correct
4 Correct 177 ms 148048 KB Output is correct
5 Correct 160 ms 148048 KB Output is correct
6 Correct 45 ms 134740 KB Output is correct
7 Correct 46 ms 134736 KB Output is correct
8 Correct 44 ms 134740 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 134736 KB Output is correct
2 Correct 50 ms 134740 KB Output is correct
3 Correct 45 ms 134740 KB Output is correct
4 Correct 45 ms 135000 KB Output is correct
5 Correct 45 ms 134932 KB Output is correct
6 Correct 45 ms 134992 KB Output is correct
7 Correct 44 ms 134740 KB Output is correct
8 Correct 47 ms 135004 KB Output is correct
9 Correct 46 ms 134996 KB Output is correct
10 Correct 46 ms 134996 KB Output is correct
11 Correct 85 ms 135764 KB Output is correct
12 Correct 44 ms 134992 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 135792 KB Output is correct
2 Correct 428 ms 135760 KB Output is correct
3 Correct 405 ms 135764 KB Output is correct
4 Correct 416 ms 135692 KB Output is correct
5 Correct 423 ms 135764 KB Output is correct
6 Correct 44 ms 134740 KB Output is correct
7 Correct 45 ms 134740 KB Output is correct
8 Correct 46 ms 134732 KB Output is correct
9 Correct 1996 ms 135792 KB Output is correct
10 Correct 46 ms 134740 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 155912 KB Output is correct
2 Correct 172 ms 155900 KB Output is correct
3 Correct 178 ms 156244 KB Output is correct
4 Correct 181 ms 157364 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 135764 KB Output is correct
2 Correct 435 ms 135864 KB Output is correct
3 Correct 408 ms 136016 KB Output is correct
4 Correct 413 ms 135764 KB Output is correct
5 Correct 429 ms 135876 KB Output is correct
6 Correct 169 ms 155884 KB Output is correct
7 Correct 178 ms 155984 KB Output is correct
8 Correct 171 ms 155984 KB Output is correct
9 Correct 204 ms 157268 KB Output is correct
10 Correct 186 ms 147996 KB Output is correct
11 Correct 158 ms 148148 KB Output is correct
12 Correct 193 ms 150876 KB Output is correct
13 Correct 164 ms 148004 KB Output is correct
14 Correct 181 ms 148048 KB Output is correct
15 Correct 48 ms 134752 KB Output is correct
16 Correct 50 ms 134736 KB Output is correct
17 Correct 47 ms 134740 KB Output is correct
18 Correct 48 ms 134992 KB Output is correct
19 Correct 46 ms 134996 KB Output is correct
20 Correct 44 ms 134992 KB Output is correct
21 Correct 46 ms 134804 KB Output is correct
22 Correct 45 ms 134992 KB Output is correct
23 Correct 45 ms 134996 KB Output is correct
24 Correct 48 ms 134992 KB Output is correct
25 Correct 84 ms 137336 KB Output is correct
26 Correct 46 ms 134808 KB Output is correct
27 Correct 1985 ms 135868 KB Output is correct
28 Correct 4362 ms 159608 KB Output is correct
29 Correct 4238 ms 155728 KB Output is correct
30 Correct 4190 ms 155724 KB Output is correct
31 Correct 4374 ms 161104 KB Output is correct
32 Correct 47 ms 134736 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 135760 KB Output is correct
2 Correct 433 ms 135636 KB Output is correct
3 Correct 410 ms 135764 KB Output is correct
4 Correct 415 ms 135760 KB Output is correct
5 Correct 434 ms 136056 KB Output is correct
6 Correct 164 ms 155988 KB Output is correct
7 Correct 166 ms 155988 KB Output is correct
8 Correct 183 ms 156104 KB Output is correct
9 Correct 189 ms 157292 KB Output is correct
10 Correct 173 ms 148016 KB Output is correct
11 Correct 172 ms 147928 KB Output is correct
12 Correct 198 ms 150864 KB Output is correct
13 Correct 168 ms 148056 KB Output is correct
14 Correct 165 ms 148048 KB Output is correct
15 Correct 2313 ms 164020 KB Output is correct
16 Execution timed out 20035 ms 165020 KB Time limit exceeded
17 Halted 0 ms 0 KB -