oj.uz

Submission #1093248

# Submission time Handle Problem Language Result Execution time Memory
1093248 2024-09-26T10:56:42 Z Wansur Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 73344 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[250], a[66];

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 = 83;
    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 125 ms 64092 KB Output is correct
2 Correct 120 ms 64116 KB Output is correct
3 Correct 157 ms 65616 KB Output is correct
4 Correct 121 ms 64024 KB Output is correct
5 Correct 129 ms 63884 KB Output is correct
6 Correct 22 ms 50984 KB Output is correct
7 Correct 23 ms 51036 KB Output is correct
8 Correct 22 ms 51032 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51036 KB Output is correct
2 Correct 22 ms 51036 KB Output is correct
3 Correct 23 ms 51068 KB Output is correct
4 Correct 22 ms 51036 KB Output is correct
5 Correct 28 ms 51136 KB Output is correct
6 Correct 24 ms 51028 KB Output is correct
7 Correct 28 ms 51032 KB Output is correct
8 Correct 23 ms 51032 KB Output is correct
9 Correct 25 ms 51052 KB Output is correct
10 Correct 23 ms 51024 KB Output is correct
11 Correct 61 ms 51968 KB Output is correct
12 Correct 24 ms 51028 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 51632 KB Output is correct
2 Correct 579 ms 51536 KB Output is correct
3 Correct 520 ms 51544 KB Output is correct
4 Correct 540 ms 51632 KB Output is correct
5 Correct 571 ms 51540 KB Output is correct
6 Correct 23 ms 51036 KB Output is correct
7 Correct 23 ms 50984 KB Output is correct
8 Correct 21 ms 50968 KB Output is correct
9 Correct 2845 ms 51636 KB Output is correct
10 Correct 21 ms 51036 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 72016 KB Output is correct
2 Correct 124 ms 72012 KB Output is correct
3 Correct 133 ms 72020 KB Output is correct
4 Correct 144 ms 72788 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 51548 KB Output is correct
2 Correct 557 ms 51588 KB Output is correct
3 Correct 534 ms 51632 KB Output is correct
4 Correct 540 ms 51536 KB Output is correct
5 Correct 578 ms 51536 KB Output is correct
6 Correct 127 ms 71788 KB Output is correct
7 Correct 123 ms 72020 KB Output is correct
8 Correct 129 ms 72288 KB Output is correct
9 Correct 151 ms 72788 KB Output is correct
10 Correct 123 ms 64092 KB Output is correct
11 Correct 120 ms 64080 KB Output is correct
12 Correct 166 ms 65616 KB Output is correct
13 Correct 131 ms 64084 KB Output is correct
14 Correct 122 ms 64088 KB Output is correct
15 Correct 23 ms 51036 KB Output is correct
16 Correct 24 ms 50944 KB Output is correct
17 Correct 22 ms 50884 KB Output is correct
18 Correct 25 ms 51036 KB Output is correct
19 Correct 25 ms 51036 KB Output is correct
20 Correct 26 ms 51028 KB Output is correct
21 Correct 25 ms 51024 KB Output is correct
22 Correct 24 ms 51036 KB Output is correct
23 Correct 28 ms 51036 KB Output is correct
24 Correct 24 ms 51152 KB Output is correct
25 Correct 65 ms 52052 KB Output is correct
26 Correct 30 ms 51024 KB Output is correct
27 Correct 2922 ms 51480 KB Output is correct
28 Correct 5205 ms 72160 KB Output is correct
29 Correct 5107 ms 68696 KB Output is correct
30 Correct 4968 ms 68740 KB Output is correct
31 Correct 5204 ms 73252 KB Output is correct
32 Correct 24 ms 51280 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 51540 KB Output is correct
2 Correct 575 ms 51636 KB Output is correct
3 Correct 521 ms 51540 KB Output is correct
4 Correct 536 ms 51548 KB Output is correct
5 Correct 578 ms 51632 KB Output is correct
6 Correct 136 ms 72020 KB Output is correct
7 Correct 126 ms 71836 KB Output is correct
8 Correct 141 ms 72032 KB Output is correct
9 Correct 157 ms 72784 KB Output is correct
10 Correct 125 ms 64080 KB Output is correct
11 Correct 117 ms 64088 KB Output is correct
12 Correct 151 ms 65620 KB Output is correct
13 Correct 136 ms 64044 KB Output is correct
14 Correct 123 ms 64088 KB Output is correct
15 Correct 2052 ms 71964 KB Output is correct
16 Execution timed out 20044 ms 73344 KB Time limit exceeded
17 Halted 0 ms 0 KB -