oj.uz

Submission #1093244

# Submission time Handle Problem Language Result Execution time Memory
1093244 2024-09-26T10:47:49 Z Wansur Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 38480 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);
        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 = 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 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 69 ms 29276 KB Output is correct
2 Correct 69 ms 29272 KB Output is correct
3 Correct 104 ms 30800 KB Output is correct
4 Correct 69 ms 29272 KB Output is correct
5 Correct 69 ms 29272 KB Output is correct
6 Correct 6 ms 16508 KB Output is correct
7 Correct 6 ms 16472 KB Output is correct
8 Correct 6 ms 16472 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16476 KB Output is correct
2 Correct 6 ms 16476 KB Output is correct
3 Correct 6 ms 16452 KB Output is correct
4 Correct 7 ms 16476 KB Output is correct
5 Correct 6 ms 16512 KB Output is correct
6 Correct 6 ms 16476 KB Output is correct
7 Correct 6 ms 16476 KB Output is correct
8 Correct 7 ms 16476 KB Output is correct
9 Correct 7 ms 16476 KB Output is correct
10 Correct 8 ms 16468 KB Output is correct
11 Correct 44 ms 17492 KB Output is correct
12 Correct 8 ms 16472 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 16988 KB Output is correct
2 Correct 664 ms 16984 KB Output is correct
3 Correct 700 ms 16988 KB Output is correct
4 Correct 704 ms 16984 KB Output is correct
5 Correct 676 ms 16992 KB Output is correct
6 Correct 7 ms 16476 KB Output is correct
7 Correct 8 ms 16476 KB Output is correct
8 Correct 7 ms 16472 KB Output is correct
9 Correct 3528 ms 16988 KB Output is correct
10 Correct 8 ms 16540 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 37212 KB Output is correct
2 Correct 80 ms 37212 KB Output is correct
3 Correct 84 ms 37040 KB Output is correct
4 Correct 128 ms 37972 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 16968 KB Output is correct
2 Correct 696 ms 16988 KB Output is correct
3 Correct 750 ms 16988 KB Output is correct
4 Correct 719 ms 16988 KB Output is correct
5 Correct 713 ms 16972 KB Output is correct
6 Correct 88 ms 36988 KB Output is correct
7 Correct 90 ms 37076 KB Output is correct
8 Correct 86 ms 37024 KB Output is correct
9 Correct 105 ms 37996 KB Output is correct
10 Correct 79 ms 29288 KB Output is correct
11 Correct 80 ms 29328 KB Output is correct
12 Correct 132 ms 30816 KB Output is correct
13 Correct 75 ms 29288 KB Output is correct
14 Correct 73 ms 29328 KB Output is correct
15 Correct 7 ms 16444 KB Output is correct
16 Correct 10 ms 16448 KB Output is correct
17 Correct 7 ms 16472 KB Output is correct
18 Correct 8 ms 16476 KB Output is correct
19 Correct 10 ms 16480 KB Output is correct
20 Correct 9 ms 16580 KB Output is correct
21 Correct 9 ms 16476 KB Output is correct
22 Correct 7 ms 16548 KB Output is correct
23 Correct 8 ms 16476 KB Output is correct
24 Correct 7 ms 16636 KB Output is correct
25 Correct 50 ms 17572 KB Output is correct
26 Correct 7 ms 16464 KB Output is correct
27 Correct 3504 ms 16996 KB Output is correct
28 Correct 12582 ms 37464 KB Output is correct
29 Correct 12720 ms 33872 KB Output is correct
30 Correct 12408 ms 33916 KB Output is correct
31 Correct 12668 ms 38480 KB Output is correct
32 Correct 7 ms 16472 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 16964 KB Output is correct
2 Correct 664 ms 16984 KB Output is correct
3 Correct 706 ms 16988 KB Output is correct
4 Correct 707 ms 16984 KB Output is correct
5 Correct 685 ms 16984 KB Output is correct
6 Correct 77 ms 37208 KB Output is correct
7 Correct 75 ms 37212 KB Output is correct
8 Correct 80 ms 37212 KB Output is correct
9 Correct 104 ms 37984 KB Output is correct
10 Correct 99 ms 29276 KB Output is correct
11 Correct 84 ms 29276 KB Output is correct
12 Correct 108 ms 30828 KB Output is correct
13 Correct 73 ms 29272 KB Output is correct
14 Correct 69 ms 29276 KB Output is correct
15 Correct 2052 ms 37204 KB Output is correct
16 Execution timed out 20034 ms 37720 KB Time limit exceeded
17 Halted 0 ms 0 KB -