oj.uz

Submission #962167

# Submission time Handle Problem Language Result Execution time Memory
962167 2024-04-13T08:17:25 Z danikoynov Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 37964 KB 
#include "wombats.h"
#include<bits/stdc++.h>

using namespace std;

const int maxr = 5010, maxc = 210;
const int maxblock = sqrt(maxr) + 10;
void precalculate();
int h[maxr][maxc], v[maxr][maxc], dp[maxblock][maxc][maxc];
int r, c, block_size;


void init(int R, int C, int H[5000][200], int V[5000][200]) {
    /* ... */
    block_size = sqrt(R) + 1;
    r = R;
    c = C;
    for (int i = 0; i < R - 1; i ++)
     for (int j = 0; j < C; j ++)
     v[i][j] = V[i][j];

    for (int i = 0; i < R; i ++)
     for (int j = 0; j < C - 1; j ++)
     h[i][j] = H[i][j];

     precalculate();

}

const int inf = 2e9 + 10;
int fp[2][maxc];
void fix_row(int i)
{
     for (int j = 1; j < c; j ++)
     {
          fp[i & 1][j] = min(fp[i & 1][j], fp[i & 1][j - 1] + h[i][j - 1]);
     }
     for (int j = c - 2; j >= 0; j --)
     {
          fp[i & 1][j] = min(fp[i & 1][j], fp[i & 1][j + 1] + h[i][j]);
     }
}


void calc_block(int bl)
{

     int st = bl * block_size;
     int en = (bl + 1) * block_size - 1;

     en = min(en, r - 1);

     for (int d = 0; d < c; d ++)
     {
          for (int j = 0; j < c; j ++)
          {
               fp[0][j] = fp[1][j] = inf;
          }

          fp[st & 1][d] = 0;
          fix_row(st);

          for (int i = st + 1; i <= en; i ++)
          {
               for (int j = 0; j < c; j ++)
               {
                    fp[i & 1][j] = fp[(i - 1) & 1][j] + v[i - 1][j];
               }
               fix_row(i);
          }

          for (int j = 0; j < c; j ++)
          {
               dp[bl][d][j] = fp[en & 1][j];
          }
     }

}


void precalculate()
{
        for (int bl = 0; bl <= (r - 1) / block_size; bl ++)
     {

         /// cout << "calc block " << endl;
          calc_block(bl);
     }
     ///exit(0);
}

void changeH(int P, int Q, int W) {
    /* ... */
    h[P][Q] = W;
    calc_block(P / block_size);
}

void changeV(int P, int Q, int W) {
    /* ... */
    v[P][Q] = W;
    calc_block(P / block_size);
}

int arr[maxc], temp[maxc];
int escape(int V1, int V2)
{
     int v1 = V1, v2 = V2;
     for (int j = 0; j < c; j ++)
          arr[j] = dp[0][v1][j];

     for (int bl = 1; bl <= (r - 1) / block_size; bl ++)
     {
          int t = bl * block_size;
          for (int j = 0; j < c; j ++)
          {
               arr[j] = arr[j] + v[t - 1][j];
          }

          for (int j = 1; j < c; j ++)
          {
               arr[j] = min(arr[j], arr[j - 1] + h[t][j - 1]);
          }
          for (int j = c - 2; j >= 0; j --)
          {
               arr[j] = min(arr[j], arr[j + 1] + h[t][j]);
          }

          for (int j = 0; j < c; j ++)
               temp[j] = inf;

          for (int j = 0; j < c; j ++)
          {
               for (int d = 0; d < c; d ++)
                    temp[j] =min(temp[j], arr[d] + dp[bl][d][j]);
          }

          for (int j = 0; j < c; j ++)
               arr[j] = temp[j];
     }

     return arr[v2];
}

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 init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:22:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   22 |     for (int i = 0; i < R; i ++)
      |     ^~~
wombats.cpp:26:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   26 |      precalculate();
      |      ^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25176 KB Output is correct
2 Correct 4 ms 25180 KB Output is correct
3 Correct 171 ms 27888 KB Output is correct
4 Correct 4 ms 25176 KB Output is correct
5 Correct 5 ms 25176 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4540 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8644 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 330 ms 10772 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 10752 KB Output is correct
2 Correct 90 ms 10584 KB Output is correct
3 Correct 99 ms 10844 KB Output is correct
4 Correct 102 ms 10844 KB Output is correct
5 Correct 98 ms 10836 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 423 ms 10844 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 30300 KB Output is correct
2 Correct 9 ms 30300 KB Output is correct
3 Correct 8 ms 30300 KB Output is correct
4 Correct 187 ms 31596 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 10776 KB Output is correct
2 Correct 96 ms 10984 KB Output is correct
3 Correct 98 ms 10856 KB Output is correct
4 Correct 100 ms 10840 KB Output is correct
5 Correct 98 ms 10840 KB Output is correct
6 Correct 8 ms 30552 KB Output is correct
7 Correct 8 ms 30296 KB Output is correct
8 Correct 8 ms 30300 KB Output is correct
9 Correct 176 ms 31716 KB Output is correct
10 Correct 4 ms 25176 KB Output is correct
11 Correct 5 ms 25180 KB Output is correct
12 Correct 177 ms 28268 KB Output is correct
13 Correct 4 ms 25180 KB Output is correct
14 Correct 4 ms 25180 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8536 KB Output is correct
20 Correct 2 ms 8536 KB Output is correct
21 Correct 2 ms 8792 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 344 ms 10948 KB Output is correct
26 Correct 2 ms 8540 KB Output is correct
27 Correct 416 ms 10852 KB Output is correct
28 Execution timed out 20068 ms 33540 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 10752 KB Output is correct
2 Correct 92 ms 10844 KB Output is correct
3 Correct 102 ms 10852 KB Output is correct
4 Correct 102 ms 10844 KB Output is correct
5 Correct 98 ms 10844 KB Output is correct
6 Correct 8 ms 30300 KB Output is correct
7 Correct 9 ms 30300 KB Output is correct
8 Correct 8 ms 30296 KB Output is correct
9 Correct 177 ms 31508 KB Output is correct
10 Correct 4 ms 25176 KB Output is correct
11 Correct 4 ms 25232 KB Output is correct
12 Correct 175 ms 27788 KB Output is correct
13 Correct 5 ms 25028 KB Output is correct
14 Correct 4 ms 25180 KB Output is correct
15 Correct 1707 ms 37964 KB Output is correct
16 Execution timed out 20096 ms 36356 KB Time limit exceeded
17 Halted 0 ms 0 KB -