Submission #395031

#	Time	Username	Problem	Language	Result	Execution time	Memory
395031		phathnv	Wombats (IOI13_wombats)	C++11	100 / 100	6022 ms	183324 KiB

wombats

#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;

const int BLOCK_SIZE = 10;

int n, m, h[5000][200], v[5000][200], d[1024][200][200], o[201];

void update(int pos, int id = 1, int l = 0, int r = 499){
    if (pos < l || r < pos)
        return;
    if (l == r){
        memset(d[id], 0x3f, sizeof(d[id]));
        for(int i = 0; i < n; i++)
            d[id][i][i] = 0;
        for(int k = pos * BLOCK_SIZE; k < (pos + 1) * BLOCK_SIZE; k++)
            for(int i = 0; i < n; i++){
                for(int j = n - 2; j >= 0; j--)
                    d[id][i][j] = min(d[id][i][j], d[id][i][j + 1] + h[k][j]);
                for(int j = 1; j < n; j++)
                    d[id][i][j] = min(d[id][i][j], d[id][i][j - 1] + h[k][j - 1]);
                for(int j = 0; j < n; j++)
                    d[id][i][j] += v[k][j];
            }
        return;
    }
    int mid = (l + r) >> 1;
    update(pos, id << 1, l, mid);
    update(pos, id << 1 | 1, mid + 1, r);
    memset(d[id], 0x3f, sizeof(d[id]));
    memset(o, 0, sizeof(o));
    o[n] = n - 1;
    for(int i = 0; i < n; i++)
        for(int j = n - 1; j >= 0; j--)
            for(int k = o[j]; k <= o[j + 1]; k++)
                if (d[id][i][j] >= d[id << 1][i][k] + d[id << 1 | 1][k][j]){
                    d[id][i][j] = d[id << 1][i][k] + d[id << 1 | 1][k][j];
                    o[j] = k;
                }
}

void init(int r, int c, int _h[5000][200], int _v[5000][200]){
    m = r;
    n = c;
    memset(h, 0x3f, sizeof(h));
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c - 1; j++)
            h[i][j] = _h[i][j];
    for(int i = 0; i < r - 1; i++)
        for(int j = 0; j < c; j++)
            v[i][j] = _v[i][j];
    for(int i = 0; i <= 499; i++)
        update(i);
}

void changeH(int p, int q, int w){
    h[p][q] = w;
    update(p / BLOCK_SIZE);
}

void changeV(int p, int q, int w){
    v[p][q] = w;
    update(p / BLOCK_SIZE);
}

int escape(int v1, int v2){
    return d[1][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