Submission #777063

#	Time	Username	Problem	Language	Result	Execution time	Memory
777063		caganyanmaz	Wombats (IOI13_wombats)	C++17	100 / 100	5719 ms	183568 KiB

wombats

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

constexpr static int MXR = 5000;
constexpr static int MXC = 200;
constexpr static int BLOCK = 10;
constexpr static int MXST = 1030;
constexpr static int INF = 2e9 + 1;
int r, c, n;
int h[MXR][MXC], v[MXR][MXC];
int st[MXST][MXC][MXC];


void update_block(int i, int start);
void merge_blocks(int res, int a, int b);

void build(int ll, int rr, int index)
{
        if (ll + 1 == rr)
        {
                update_block(index, ll);
                return;
        }
        int m = ll+rr>>1;
        build(ll, m, index<<1);
        build(m, rr, (index<<1)|1);
        merge_blocks(index, index<<1, (index<<1)|1);
}

void update(int ll, int rr, int index, int i)
{
        if (rr == i+1 && ll == i)
        {
                update_block(index, i);
                return;
        }
        if (i >= rr || ll > i)
                return;
        int m = ll+rr>>1;
        update(ll, m, index<<1, i);
        update(m, rr, (index<<1)|1, i);
        merge_blocks(index, index<<1, (index<<1)|1);
}

void init(int R, int C, int H[MXR][MXC], int V[MXR][MXC])
{
        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];
        n = r / BLOCK;
        if (r % BLOCK)
                n++;
        build(0, n, 1);
}

void changeH(int P, int Q, int W)
{
        h[P][Q] = W;
        update(0, n, 1, P/BLOCK);
        if (P/BLOCK)
                update(0, n, 1, (P/BLOCK)-1);
}

void changeV(int P, int Q, int W)
{
        v[P][Q] = W;
        update(0, n, 1, P/BLOCK);
}

int escape(int V1, int V2)
{
        return st[1][V1][V2];
}

void update_block(int x, int start)
{
        int ss = start * BLOCK;
        int ee = min((start+1) * BLOCK, r-1);
        for (int i = 0; i < c; i++)
        {
                int prefix = 0;
                for (int j = i; j < c; j++)
                {
                        st[x][i][j] = st[x][j][i] = prefix;
                        prefix += h[ss][j];
                }
        }
        for (int i = ss+1; i <= ee; i++)
        {
                for (int j = 0; j < c; j++)
                {
                        for (int k = 0; k < c; k++)
                                st[x][j][k] += v[i-1][k];
                        for (int k = 1; k < c; k++)
                                st[x][j][k] = min(st[x][j][k], st[x][j][k-1] + h[i][k-1]);
                        for (int k = c-2; k >= 0; k--)
                                st[x][j][k] = min(st[x][j][k], st[x][j][k+1] + h[i][k]);
                }
        }
}

int opt[MXC][MXC];
void merge_blocks(int res, int a, int b)
{
        for (int i = c-1; i >= 0; i--)
        {
                for (int j = i; j < c; j++)
                {
                        int ss = (i==j) ? 0 : opt[i][j-1];
                        int ee = (i==j) ? c-1 : opt[i+1][j];
                        opt[i][j] = ss;
                        st[res][i][j] = st[a][i][ss] + st[b][ss][j];
                        for (int k = ss+1; k <= ee; k++)
                        {
                                int val = st[a][i][k] + st[b][k][j];
                                if (st[res][i][j] > val)
                                {
                                        opt[i][j] = k;
                                        st[res][i][j] = val;
                                }
                        }
                }
        }
        for (int j = c-1; j >= 0; j--)
        {
                for (int i = j+1; i < c; i++)
                {
                        opt[i][j] = opt[i-1][j];
                        st[res][i][j] = st[a][i][opt[i][j]] + st[b][opt[i][j]][j];
                        for (int k = opt[i][j]+1; k <= opt[i][j+1]; k++)
                        {
                                int val = st[a][i][k] + st[b][k][j];
                                if (st[res][i][j] > val)
                                {
                                        opt[i][j] = k;
                                        st[res][i][j] = val;
                                }
                        }
                }
        }
}

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;
      |      ^~~
wombats.cpp: In function 'void build(int, int, int)':
wombats.cpp:25:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         int m = ll+rr>>1;
      |                 ~~^~~
wombats.cpp: In function 'void update(int, int, int, int)':
wombats.cpp:40:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int m = ll+rr>>1;
      |                 ~~^~~

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