Submission #281562

#	Time	Username	Problem	Language	Result	Execution time	Memory
281562		Kastanda	Wombats (IOI13_wombats)	C++11	100 / 100	7611 ms	109048 KiB

wombats

// M
#include<bits/stdc++.h>
#include "wombats.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 5005, M = 202, MXS = 512, SQ = 20, INF = 1e9 + 9;
int n, m, H[N][M], V[N][M];
int dp[MXS][M][M];
int TMp[M][M], Opt[M][M];
inline void BuildBlock(int l, int r)
{
        memset(TMp, 63, sizeof(TMp));
        for (int st = 0; st < m; st ++)
        {
                TMp[st][st] = 0;
                for (int i = l; i < r; i ++)
                {
                        for (int j = 1; j < m; j ++)
                                TMp[st][j] = min(TMp[st][j], TMp[st][j - 1] + H[i][j - 1]);
                        for (int j = m - 2; j >= 0; j --)
                                TMp[st][j] = min(TMp[st][j], TMp[st][j + 1] + H[i][j]);
                        for (int j = 0; j < m; j ++)
                                TMp[st][j] += V[i][j];
                }
        }
}
inline void Merge(int id, int le, int ri)
{
        for (int sm = - m; sm < m; sm ++)
                for (int st = 0; st < m; st ++)
                {
                        int fn = sm + st;
                        if (fn < 0 || fn >= m)
                                continue;
                        int l = fn ? Opt[st][fn - 1] : 0;
                        int r = (st + 1 < m) ? Opt[st + 1][fn] : (m - 1);
                        int opt = -1, Mn = INF;
                        for (int i = l; i <= r; i ++)
                                if (Mn > dp[le][st][i] + dp[ri][i][fn])
                                        Mn = dp[le][st][i] + dp[ri][i][fn], opt = i;
                        Opt[st][fn] = opt;
                        dp[id][st][fn] = Mn;
                }
}
void BuildSegTree(int id = 1, int l = 0, int r = n)
{
        if (r - l <= SQ)
        {
                BuildBlock(l, r);
                memcpy(dp[id], TMp, sizeof(TMp));
                return ;
        }
        BuildSegTree(lc, l, md);
        BuildSegTree(rc, md, r);
        Merge(id, lc, rc);
}
void init(int _n, int _m, int _H[5000][200], int _V[5000][200])
{
        n = _n; m = _m;
        for (int i = 0; i < n; i ++)
                for (int j = 0; j + 1 < m; j ++)
                        H[i][j] = _H[i][j];
        for (int i = 0; i + 1 < n; i ++)
                for (int j = 0; j < m; j ++)
                        V[i][j] = _V[i][j];

        BuildSegTree();
}
void Update(int i, int id = 1, int l = 0, int r = n)
{
        if (r - l <= SQ)
        {
                BuildBlock(l, r);
                memcpy(dp[id], TMp, sizeof(TMp));
                return ;
        }
        if (i < md)
                Update(i, lc, l, md);
        else
                Update(i, rc, md, r);
        Merge(id, lc, rc);
}
void changeH(int r, int c, int w)
{
        H[r][c] = w;
        Update(r);
}
void changeV(int r, int c, int w)
{
        V[r][c] = w;
        Update(r);
}
int escape(int st, int fn)
{
        return dp[1][st][fn];
}

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