oj.uz

Submission #1093247

# Submission time Handle Problem Language Result Execution time Memory
1093247 2024-09-26T10:55:01 Z Wansur Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 49236 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[133], a[33];

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 = 167;
    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 96 ms 39772 KB Output is correct
2 Correct 92 ms 39768 KB Output is correct
3 Correct 126 ms 41552 KB Output is correct
4 Correct 91 ms 39772 KB Output is correct
5 Correct 90 ms 39996 KB Output is correct
6 Correct 11 ms 26968 KB Output is correct
7 Correct 11 ms 26972 KB Output is correct
8 Correct 11 ms 26972 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26968 KB Output is correct
2 Correct 11 ms 26968 KB Output is correct
3 Correct 12 ms 26924 KB Output is correct
4 Correct 11 ms 26972 KB Output is correct
5 Correct 11 ms 26972 KB Output is correct
6 Correct 13 ms 27044 KB Output is correct
7 Correct 14 ms 27036 KB Output is correct
8 Correct 12 ms 26972 KB Output is correct
9 Correct 13 ms 26972 KB Output is correct
10 Correct 11 ms 26972 KB Output is correct
11 Correct 55 ms 27984 KB Output is correct
12 Correct 12 ms 26968 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 27512 KB Output is correct
2 Correct 665 ms 27484 KB Output is correct
3 Correct 712 ms 27484 KB Output is correct
4 Correct 707 ms 27484 KB Output is correct
5 Correct 677 ms 27520 KB Output is correct
6 Correct 12 ms 26968 KB Output is correct
7 Correct 12 ms 26972 KB Output is correct
8 Correct 12 ms 26932 KB Output is correct
9 Correct 3482 ms 27524 KB Output is correct
10 Correct 12 ms 26972 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 47704 KB Output is correct
2 Correct 97 ms 47708 KB Output is correct
3 Correct 98 ms 47704 KB Output is correct
4 Correct 121 ms 48720 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 27508 KB Output is correct
2 Correct 670 ms 27512 KB Output is correct
3 Correct 730 ms 27484 KB Output is correct
4 Correct 715 ms 27516 KB Output is correct
5 Correct 689 ms 27484 KB Output is correct
6 Correct 95 ms 47708 KB Output is correct
7 Correct 99 ms 47696 KB Output is correct
8 Correct 102 ms 47708 KB Output is correct
9 Correct 117 ms 48692 KB Output is correct
10 Correct 93 ms 39768 KB Output is correct
11 Correct 90 ms 39772 KB Output is correct
12 Correct 127 ms 41552 KB Output is correct
13 Correct 94 ms 39996 KB Output is correct
14 Correct 92 ms 39772 KB Output is correct
15 Correct 13 ms 26972 KB Output is correct
16 Correct 11 ms 26936 KB Output is correct
17 Correct 11 ms 26968 KB Output is correct
18 Correct 11 ms 27216 KB Output is correct
19 Correct 15 ms 27024 KB Output is correct
20 Correct 12 ms 26968 KB Output is correct
21 Correct 12 ms 26972 KB Output is correct
22 Correct 15 ms 26972 KB Output is correct
23 Correct 12 ms 26972 KB Output is correct
24 Correct 13 ms 27108 KB Output is correct
25 Correct 51 ms 28132 KB Output is correct
26 Correct 12 ms 26968 KB Output is correct
27 Correct 3489 ms 27516 KB Output is correct
28 Correct 7680 ms 48204 KB Output is correct
29 Correct 7687 ms 44628 KB Output is correct
30 Correct 7251 ms 44592 KB Output is correct
31 Correct 7649 ms 49236 KB Output is correct
32 Correct 12 ms 26972 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 27480 KB Output is correct
2 Correct 631 ms 27516 KB Output is correct
3 Correct 708 ms 27480 KB Output is correct
4 Correct 711 ms 27728 KB Output is correct
5 Correct 693 ms 27516 KB Output is correct
6 Correct 97 ms 47696 KB Output is correct
7 Correct 99 ms 47704 KB Output is correct
8 Correct 107 ms 47708 KB Output is correct
9 Correct 118 ms 48568 KB Output is correct
10 Correct 92 ms 39996 KB Output is correct
11 Correct 90 ms 39772 KB Output is correct
12 Correct 126 ms 41560 KB Output is correct
13 Correct 90 ms 39768 KB Output is correct
14 Correct 93 ms 39996 KB Output is correct
15 Correct 1908 ms 47828 KB Output is correct
16 Execution timed out 20051 ms 48968 KB Time limit exceeded
17 Halted 0 ms 0 KB -