oj.uz

Submission #280360

# Submission time Handle Problem Language Result Execution time Memory
280360 2020-08-22T16:45:42 Z Kastanda Wombats (IOI13_wombats) C++11
39 / 100
 20000 ms 29040 KB 
// 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

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8576 KB Output is correct
2 Correct 10 ms 8576 KB Output is correct
3 Correct 1799 ms 10580 KB Output is correct
4 Correct 11 ms 8576 KB Output is correct
5 Correct 10 ms 8576 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 231 ms 2040 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3859 ms 948 KB Output is correct
2 Correct 6070 ms 940 KB Output is correct
3 Correct 7691 ms 952 KB Output is correct
4 Correct 7214 ms 960 KB Output is correct
5 Correct 8457 ms 1016 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Execution timed out 20085 ms 888 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16512 KB Output is correct
2 Correct 27 ms 16512 KB Output is correct
3 Correct 28 ms 16520 KB Output is correct
4 Correct 955 ms 17620 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3827 ms 1000 KB Output is correct
2 Correct 5911 ms 1016 KB Output is correct
3 Correct 7482 ms 1144 KB Output is correct
4 Correct 7123 ms 888 KB Output is correct
5 Correct 8481 ms 964 KB Output is correct
6 Correct 26 ms 16512 KB Output is correct
7 Correct 25 ms 16512 KB Output is correct
8 Correct 25 ms 16632 KB Output is correct
9 Correct 917 ms 17784 KB Output is correct
10 Correct 11 ms 8576 KB Output is correct
11 Correct 11 ms 8576 KB Output is correct
12 Correct 1744 ms 10744 KB Output is correct
13 Correct 11 ms 8576 KB Output is correct
14 Correct 11 ms 8576 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 2 ms 432 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 222 ms 1940 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Execution timed out 20051 ms 888 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3811 ms 980 KB Output is correct
2 Correct 5884 ms 988 KB Output is correct
3 Correct 7601 ms 956 KB Output is correct
4 Correct 7134 ms 1016 KB Output is correct
5 Correct 8413 ms 956 KB Output is correct
6 Correct 25 ms 16512 KB Output is correct
7 Correct 26 ms 16512 KB Output is correct
8 Correct 28 ms 16564 KB Output is correct
9 Correct 934 ms 17884 KB Output is correct
10 Correct 10 ms 8576 KB Output is correct
11 Correct 12 ms 8576 KB Output is correct
12 Correct 1772 ms 10632 KB Output is correct
13 Correct 10 ms 8576 KB Output is correct
14 Correct 10 ms 8576 KB Output is correct
15 Incorrect 12175 ms 29040 KB Output isn't correct
16 Halted 0 ms 0 KB -