Submission #439114

#	Time	Username	Problem	Language	Result	Execution time	Memory
439114		prvocislo	Wombats (IOI13_wombats)	C++17	100 / 100	4389 ms	195356 KiB

wombats

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

const int R = 5120, C = 205, B = 10, V = 512, inf = 1e9 + 5;
//const int R = 4, C = 4, B = 1, V = 4, inf = 1e9 + 5;
int h[R][C], v[R][C], st[V*2][C][C], l[V*2], r[V*2], o[C+1];
void print(string s, int m[C][C])
{
    cout << s << "\n";
    for (int i = 0; i < C; i++) for (int j = 0; j < C; j++) cout << m[i][j] << " \n"[j==C-1];
    cout << "\n";
}
void upd(int &a, const int &b) { a = min(a, b); }
void update(int li, int ri, int vr = 0)
{
    if (ri < l[vr] || li > r[vr]) return; // tento update sa ma netyka
    if (l[vr] == r[vr]) // dosli sme na list
    {
        for (int i = 0; i < C; i++) for (int j = 0; j < C; j++) st[vr][i][j] = inf;
        for (int c1 = 0; c1 < C; c1++)
        {
            st[vr][c1][c1] = 0;
            for (int i = l[vr] * B; i < (r[vr] + 1) * B; i++)
            {
                for (int c2 = 0; c2 < C - 1; c2++) upd(st[vr][c1][c2 + 1], st[vr][c1][c2] + h[i][c2]);
                for (int c2 = C - 1; c2 > 0; c2--) upd(st[vr][c1][c2 - 1], st[vr][c1][c2] + h[i][c2 - 1]);
                for (int c2 = 0; c2 < C; c2++) st[vr][c1][c2] += v[i][c2];
            }
        }
        //print("leaf " + to_string(vr) + ":", st[vr]);
        return;
    }
    update(li, ri, vr * 2 + 1), update(li, ri, vr * 2 + 2);
    fill(o, o + C, 0); o[C] = C - 1;
    for (int c1 = 0; c1 < C; c1++) for (int c2 = C - 1; c2 >= 0; c2--)
    {
        pair<int, int> best(inf, -o[c2]); // kde sme nasli minimalnu hodnotu a jej index
        for (int k = o[c2]; k <= o[c2 + 1]; k++) 
            best = min(best, {st[vr*2+1][c1][k]+st[vr*2+2][k][c2], -k});
        st[vr][c1][c2] = best.first;
        o[c2] = -best.second;
    }
    //print("non-leaf " + to_string(vr) + ":", st[vr]);
}
void init(int ri, int ci, int h[5000][200], int v[5000][200]) {
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) ::h[i][j] = inf;
    for (int i = V - 1; i < V * 2; i++) l[i] = r[i] = i - (V - 1);
    for (int i = V - 2; i >= 0; i--) l[i] = l[i*2+1], r[i] = r[i*2+2];
    for (int i = 0; i < ri; i++) for (int j = 0; j < ci - 1; j++) ::h[i][j] = h[i][j];
    for (int i = 0; i < ri - 1; i++) for (int j = 0; j < ci; j++) ::v[i][j] = v[i][j];
    update(0, V - 1);
}
void changeH(int i, int j, int val) {
    h[i][j] = val;
    update(i/B, i/B);
}
void changeV(int i, int j, int val) {
    v[i][j] = val;
    update(i/B, i/B);
}
int escape(int v1, int v2) {
    return st[0][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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24