Submission #1242991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242991		gs13105	Wombats (IOI13_wombats)	C++20	76 / 100	20085 ms	20084 KiB

wombats

#include <bits/stdc++.h>
using namespace std;

#include "wombats.h"

const int INF = 1e9;
const int B = 250;
int R, C;
int H[5001][200];
int V[5001][200];

int mem[5000 / B + 1][200][200];
int dp1[200];
void upd(int b)
{
    int s = b * B;
    int l = min(B, R - s);
    for(int i = 0; i < C; i++)
    {
        for(int j = 0; j < C; j++)
            dp1[j] = INF;
        dp1[i] = 0;
        for(int j = 0; j < l; j++)
        {
            for(int k = 1; k < C; k++)
                dp1[k] = min(dp1[k], dp1[k - 1] + H[j + s][k - 1]);
            for(int k = C - 2; k >= 0; k--)
                dp1[k] = min(dp1[k], dp1[k + 1] + H[j + s][k]);
            for(int k = 0; k < C; k++)
                dp1[k] += V[j + s][k];
        }
        for(int j = 0; j < C; j++)
            mem[b][i][j] = dp1[j];
    }
}

void init(int _R, int _C, int _H[5000][200], int _V[5000][200])
{
    R = _R;
    C = _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 < (R + B - 1) / B; i++)
        upd(i);
}

void changeH(int P, int Q, int W)
{
    H[P][Q] = W;
    upd(P / B);
}

void changeV(int P, int Q, int W)
{
    V[P][Q] = W;
    upd(P / B);
}

int dp2[5000 / B + 1][200];
int fb;
void f(int l, int r, int s, int g)
{
    if(r < l)
        return;
    int x = (l + r) / 2, p = s;
    dp2[fb][x] = INF;
    for(int i = s; i <= g; i++)
    {
        int t = dp2[fb - 1][i] + mem[fb][i][x];
        if(t < dp2[fb][x])
        {
            dp2[fb][x] = t;
            p = i;
        }
    }
    f(l, x - 1, s, p);
    f(x + 1, r, p, g);
}

int escape(int V1, int V2)
{
    for(int i = 0; i < C; i++)
        dp2[0][i] = mem[0][V1][i];
    for(int i = 1; i < (R + B - 1) / B; i++)
    {
        fb = i;
        f(0, C - 1, 0, C - 1);
    }
    return dp2[(R - 1) / B][V2];
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24