oj.uz

Submission #1025430

# Submission time Handle Problem Language Result Execution time Memory
1025430 2024-07-17T03:13:52 Z socpite Wombats (IOI13_wombats) C++17
100 / 100
 12039 ms 115544 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;

const int maxr = 5005;
const int maxc = 205;
const int INF = 1e9+5;

int pos[maxc][maxc];

int n, m;

int WH[maxr][maxc];
int WV[maxr][maxc];

struct matrix{
    int a[maxc][maxc];
    matrix(){}
    matrix operator*(const matrix &rhs){
        matrix re;
        for(int d = m-1; d >= 0; d--){
            for(int i = 0; i+d < m; i++){
                int j = i + d, l, r;
                re.a[i][j] = INF;
                
                if(i == 0)l = 0;
                else l = pos[i-1][j];
                if(j == m-1)r = m-1;
                else r = m-1;

                for(int k = l; k <= r; k++){
                    if(a[i][k] + rhs.a[k][j] < re.a[i][j]){
                        re.a[i][j] = a[i][k] + rhs.a[k][j];
                        pos[i][j] = k;
                    }
                }
            }
        }
        for(int d = m-1; d > 0; d--){
            for(int j = 0; j+d < m; j++){
                int i = j + d, l, r;
                re.a[i][j] = INF;

                if(j == 0)l = 0;
                else l = pos[i][j-1];
                if(i == m-1)r = m-1;
                else r = pos[i+1][j];

                for(int k = l; k <= r; k++){
                    if(a[i][k] + rhs.a[k][j] < re.a[i][j]){
                        re.a[i][j] = a[i][k] + rhs.a[k][j];
                        pos[i][j] = k;
                    }
                }
            }
        }
        return re;
    }
    matrix(int l, int r){
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                a[i][j] = (i == j ? 0 : INF);
            }
        }
        for(int k = l; k <= r; k++){
            for(int i = 0; i < m; i++){
                for(int j = 1; j < m; j++){
                    a[i][j] = min(a[i][j], a[i][j-1] + WH[k][j-1]);
                }
                for(int j = m-2; j >= 0; j--){
                    a[i][j] = min(a[i][j], a[i][j+1] + WH[k][j]);
                }
            }
            for(int i = 0; i < m; i++){
                for(int j = 0; j < m; j++){
                    a[i][j] += WV[k][j];
                    // cout << i << " " << j << " " << a[i][j] << endl;
                }
            }
        }
    }
}st[1005];

const int BLSZ = 32;

void build(int l = 0, int r = n - 1, int id = 1){
    if(r - l + 1 <= BLSZ)st[id] = matrix(l, r);
    else {
        int mid = (l+r)>>1;
        build(l, mid, id<<1);
        build(mid+1, r, id<<1|1);
        st[id] = st[id<<1]*st[id<<1|1];
    }
}

void edit(int k, int l = 0, int r = n-1, int id = 1){
    if(r - l + 1 <= BLSZ)st[id] = matrix(l, r);
    else {
        int mid = (l+r)>>1;
        if(k <= mid)edit(k, l, mid, id<<1);
        else edit(k, mid+1, r, id<<1|1);
        st[id] = st[id<<1]*st[id<<1|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++)WH[i][j] = H[i][j];
    }
    for(int i = 0; i < n-1; i++){
        for(int j = 0; j < m; j++)WV[i][j] = V[i][j];
    }
    build();
}

void changeH(int P, int Q, int W) {
    WH[P][Q] = W;
    edit(P);
}

void changeV(int P, int Q, int W) {
    WV[P][Q] = W;
    edit(P);
}

int escape(int V1, int V2) {
    return st[1].a[V1][V2];
}

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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100024 KB Output is correct
2 Correct 48 ms 99928 KB Output is correct
3 Correct 90 ms 102736 KB Output is correct
4 Correct 53 ms 99932 KB Output is correct
5 Correct 48 ms 99928 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 8924 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8900 KB Output is correct
8 Correct 1 ms 8904 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 9052 KB Output is correct
11 Correct 39 ms 11224 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 11868 KB Output is correct
2 Correct 262 ms 11912 KB Output is correct
3 Correct 203 ms 11900 KB Output is correct
4 Correct 208 ms 11868 KB Output is correct
5 Correct 209 ms 11868 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 962 ms 11868 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 104588 KB Output is correct
2 Correct 50 ms 104540 KB Output is correct
3 Correct 53 ms 104540 KB Output is correct
4 Correct 70 ms 105812 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 11900 KB Output is correct
2 Correct 244 ms 11924 KB Output is correct
3 Correct 207 ms 11908 KB Output is correct
4 Correct 208 ms 11868 KB Output is correct
5 Correct 202 ms 12120 KB Output is correct
6 Correct 48 ms 104536 KB Output is correct
7 Correct 51 ms 104540 KB Output is correct
8 Correct 56 ms 104540 KB Output is correct
9 Correct 72 ms 105812 KB Output is correct
10 Correct 46 ms 99932 KB Output is correct
11 Correct 75 ms 99912 KB Output is correct
12 Correct 105 ms 102736 KB Output is correct
13 Correct 55 ms 99928 KB Output is correct
14 Correct 48 ms 99932 KB Output is correct
15 Correct 1 ms 4696 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 8796 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 1 ms 8796 KB Output is correct
21 Correct 1 ms 8796 KB Output is correct
22 Correct 1 ms 8796 KB Output is correct
23 Correct 1 ms 8796 KB Output is correct
24 Correct 1 ms 8796 KB Output is correct
25 Correct 39 ms 11348 KB Output is correct
26 Correct 2 ms 8796 KB Output is correct
27 Correct 948 ms 11928 KB Output is correct
28 Correct 1816 ms 108580 KB Output is correct
29 Correct 2268 ms 66640 KB Output is correct
30 Correct 2099 ms 66896 KB Output is correct
31 Correct 1960 ms 110432 KB Output is correct
32 Correct 2 ms 8796 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 11864 KB Output is correct
2 Correct 243 ms 11892 KB Output is correct
3 Correct 232 ms 11864 KB Output is correct
4 Correct 203 ms 12112 KB Output is correct
5 Correct 224 ms 11924 KB Output is correct
6 Correct 55 ms 104536 KB Output is correct
7 Correct 49 ms 104540 KB Output is correct
8 Correct 53 ms 104540 KB Output is correct
9 Correct 71 ms 105892 KB Output is correct
10 Correct 48 ms 99928 KB Output is correct
11 Correct 46 ms 99932 KB Output is correct
12 Correct 83 ms 102672 KB Output is correct
13 Correct 55 ms 100028 KB Output is correct
14 Correct 48 ms 99932 KB Output is correct
15 Correct 1961 ms 114372 KB Output is correct
16 Correct 11386 ms 115544 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4700 KB Output is correct
20 Correct 1 ms 8796 KB Output is correct
21 Correct 1 ms 8796 KB Output is correct
22 Correct 1 ms 8928 KB Output is correct
23 Correct 2 ms 8996 KB Output is correct
24 Correct 1 ms 8796 KB Output is correct
25 Correct 1 ms 8796 KB Output is correct
26 Correct 1 ms 8796 KB Output is correct
27 Correct 48 ms 11348 KB Output is correct
28 Correct 2 ms 8796 KB Output is correct
29 Correct 954 ms 11908 KB Output is correct
30 Correct 1794 ms 108624 KB Output is correct
31 Correct 8908 ms 113028 KB Output is correct
32 Correct 8802 ms 112912 KB Output is correct
33 Correct 2408 ms 66676 KB Output is correct
34 Correct 11968 ms 70548 KB Output is correct
35 Correct 2236 ms 66940 KB Output is correct
36 Correct 11721 ms 70884 KB Output is correct
37 Correct 1924 ms 110420 KB Output is correct
38 Correct 12039 ms 113668 KB Output is correct
39 Correct 1 ms 8792 KB Output is correct
40 Correct 10678 ms 70760 KB Output is correct