oj.uz

Submission #1093240

# Submission time Handle Problem Language Result Execution time Memory
1093240 2024-09-26T10:36:40 Z Wansur Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 38740 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[40], a[10];

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 = 625;
    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

# Verdict Execution time Memory Grader output
1 Correct 104 ms 21168 KB Output is correct
2 Correct 79 ms 21080 KB Output is correct
3 Correct 113 ms 23892 KB Output is correct
4 Correct 68 ms 21084 KB Output is correct
5 Correct 67 ms 21176 KB Output is correct
6 Correct 7 ms 8540 KB Output is correct
7 Correct 6 ms 8536 KB Output is correct
8 Correct 4 ms 8536 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 4 ms 8536 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8700 KB Output is correct
5 Correct 4 ms 8536 KB Output is correct
6 Correct 6 ms 8536 KB Output is correct
7 Correct 4 ms 8540 KB Output is correct
8 Correct 6 ms 8540 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct
11 Correct 43 ms 10836 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 9048 KB Output is correct
2 Correct 666 ms 9052 KB Output is correct
3 Correct 706 ms 9092 KB Output is correct
4 Correct 706 ms 9072 KB Output is correct
5 Correct 667 ms 9048 KB Output is correct
6 Correct 7 ms 8444 KB Output is correct
7 Correct 4 ms 8540 KB Output is correct
8 Correct 4 ms 8536 KB Output is correct
9 Correct 3452 ms 9072 KB Output is correct
10 Correct 4 ms 8536 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 29144 KB Output is correct
2 Correct 78 ms 29020 KB Output is correct
3 Correct 77 ms 29148 KB Output is correct
4 Correct 100 ms 30420 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 9052 KB Output is correct
2 Correct 668 ms 9052 KB Output is correct
3 Correct 700 ms 9048 KB Output is correct
4 Correct 707 ms 9072 KB Output is correct
5 Correct 667 ms 9048 KB Output is correct
6 Correct 80 ms 29016 KB Output is correct
7 Correct 82 ms 29132 KB Output is correct
8 Correct 84 ms 29020 KB Output is correct
9 Correct 118 ms 30288 KB Output is correct
10 Correct 66 ms 21084 KB Output is correct
11 Correct 66 ms 21080 KB Output is correct
12 Correct 108 ms 23892 KB Output is correct
13 Correct 69 ms 21080 KB Output is correct
14 Correct 65 ms 20972 KB Output is correct
15 Correct 3 ms 8540 KB Output is correct
16 Correct 3 ms 8456 KB Output is correct
17 Correct 3 ms 8540 KB Output is correct
18 Correct 4 ms 8540 KB Output is correct
19 Correct 4 ms 8540 KB Output is correct
20 Correct 4 ms 8536 KB Output is correct
21 Correct 3 ms 8536 KB Output is correct
22 Correct 4 ms 8536 KB Output is correct
23 Correct 3 ms 8536 KB Output is correct
24 Correct 4 ms 8536 KB Output is correct
25 Correct 43 ms 10836 KB Output is correct
26 Correct 4 ms 8536 KB Output is correct
27 Correct 3494 ms 9084 KB Output is correct
28 Execution timed out 20041 ms 32908 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 9048 KB Output is correct
2 Correct 661 ms 9048 KB Output is correct
3 Correct 724 ms 9072 KB Output is correct
4 Correct 700 ms 9072 KB Output is correct
5 Correct 675 ms 9072 KB Output is correct
6 Correct 106 ms 29020 KB Output is correct
7 Correct 80 ms 29020 KB Output is correct
8 Correct 77 ms 29016 KB Output is correct
9 Correct 99 ms 30288 KB Output is correct
10 Correct 64 ms 21084 KB Output is correct
11 Correct 65 ms 21084 KB Output is correct
12 Correct 112 ms 24144 KB Output is correct
13 Correct 64 ms 20976 KB Output is correct
14 Correct 66 ms 21084 KB Output is correct
15 Correct 2304 ms 38740 KB Output is correct
16 Execution timed out 20051 ms 37404 KB Time limit exceeded
17 Halted 0 ms 0 KB -