Submission #1025430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025430		socpite	Wombats (IOI13_wombats)	C++17	100 / 100	12039 ms	115544 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24