Submission #394997

#	Time	Username	Problem	Language	Result	Execution time	Memory
394997		phathnv	웜뱃 (IOI13_wombats)	C++11	0 / 100	515 ms	19020 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], dp[200][200], o[201];

void update(int pos, int id = 1, int l = 0, int r = (m - 1) / 10){
    if (pos < l || r < pos)
        return;
    if (l == r){
        memset(dp, 0x3f, sizeof(dp));
        for(int i = 0; i < n; i++)
            dp[i][i] = 0;
        for(int r = pos * BLOCK_SIZE; r < min((pos + 1) * BLOCK_SIZE, m); r++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n - 1; j++)
                    dp[i][j] = min(dp[i][j], dp[i][j + 1] + h[r][j]);
                for(int j = 0; j < n - 1; j++)
                    dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + h[r][j]);
            }
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    dp[i][j] += v[r][j];
        }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                d[id][i][j] = dp[i][j];
        return;
    }
    int mid = (l + r) >> 1;
    update(pos, id << 1, l, mid);
    update(pos, id << 1 | 1, mid + 1, r);
    memset(dp[id], 0x3f, sizeof(dp[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 = 0; k < n; 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];
                }
}

void init(int r, int c, int _h[5000][200], int _v[5000][200]){
    m = r;
    n = c;
    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 <= m / BLOCK_SIZE; 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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24