Submission #280360

#	Time	Username	Problem	Language	Result	Execution time	Memory
280360		Kastanda	Wombats (IOI13_wombats)	C++11	39 / 100	20085 ms	29040 KiB

wombats

// M
#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;
const int N = 5005, M = 202, SQ = 70, QS = N / SQ;
int n, m, H[N][M], V[N][M];
int DS[QS][M][M];
int D[M], D2[M];
priority_queue < pair < int , int > > Pq;
inline void Build(int block)
{
        int l = block * SQ;
        int r = min(l + SQ, n);

        for (int st = 0; st < m; st ++)
        {
                memset(D, 63, sizeof(D));
                D[st] = 0;
                for (int i = l; i < r; i ++)
                {
                        for (int j = 0; j < m; j ++)
                                Pq.push({-D[j], j});
                        while (Pq.size())
                        {
                                int d = -Pq.top().first;
                                int v = Pq.top().second;
                                Pq.pop();
                                if (d > D[v])
                                        continue;
                                if (v > 0 && D[v] + H[i][v - 1] < D[v - 1])
                                        D[v - 1] = D[v] + H[i][v - 1], Pq.push({-D[v - 1], v - 1});
                                if (v + 1 < m && D[v] + H[i][v] < D[v + 1])
                                        D[v + 1] = D[v] + H[i][v], Pq.push({-D[v + 1], v + 1});
                        }
                        for (int j = 0; j < m; j ++)
                                D[j] += V[i][j];
                }
                for (int j = 0; j < m; j ++)
                        DS[block][st][j] = D[j];
        }
}
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];

        for (int i = 0; i < n; i += SQ)
                Build(i / SQ);
}

void changeH(int r, int c, int w)
{
        H[r][c] = w;
        Build(r / SQ);
}

void changeV(int r, int c, int w)
{
        V[r][c] = w;
        Build(r / SQ);
}

int escape(int st, int fn)
{
        memset(D, 63, sizeof(D));
        D[st] = 0;

        for (int i = 0; i <= (n - 1) / SQ; i ++)
        {
                memset(D2, 63, sizeof(D2));
                for (int j = 0; j < m; j ++)
                        for (int jto = 0; jto < m; jto ++)
                                D2[jto] = min(D2[jto], D[j] + DS[i][j][jto]);
                memcpy(D, D2, sizeof(D));
        }

        return D[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: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24