oj.uz

Submission #777061

# Submission time Handle Problem Language Result Execution time Memory
777061 2023-07-08T15:02:03 Z caganyanmaz Wombats (IOI13_wombats) C++17
28 / 100
 662 ms 32852 KB 
#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 = 521;
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

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 17104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 54 ms 2764 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 2244 KB Output is correct
2 Correct 93 ms 2260 KB Output is correct
3 Correct 184 ms 2356 KB Output is correct
4 Correct 115 ms 2260 KB Output is correct
5 Correct 128 ms 2336 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 662 ms 2380 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 32800 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 2352 KB Output is correct
2 Correct 94 ms 2332 KB Output is correct
3 Correct 181 ms 2352 KB Output is correct
4 Correct 104 ms 2356 KB Output is correct
5 Correct 127 ms 2348 KB Output is correct
6 Runtime error 22 ms 32852 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 2352 KB Output is correct
2 Correct 93 ms 2324 KB Output is correct
3 Correct 182 ms 2364 KB Output is correct
4 Correct 109 ms 2368 KB Output is correct
5 Correct 125 ms 2344 KB Output is correct
6 Runtime error 25 ms 32804 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -