oj.uz

Submission #1067823

# Submission time Handle Problem Language Result Execution time Memory
1067823 2024-08-21T04:02:48 Z 12345678 Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 24836 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=5e3+5, cx=2e2+5;

int r, c, ver[nx][cx], horr[nx][cx], horl[nx][cx], dp[nx][cx];

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r=R, c=C;
    for (int i=0; i<R-1; i++) for (int j=0; j<C; j++) ver[i][j]=V[i][j];
    for (int i=0; i<R; i++) for (int j=0; j<C-1; j++) horr[i][j]=H[i][j], horl[i][j+1]=H[i][j];
}

void changeH(int P, int Q, int W) {
    horr[P][Q]=W;
    horl[P][Q+1]=W;
}

void changeV(int P, int Q, int W) {
    ver[P][Q]=W;
}

int escape(int V1, int V2) {
    for (int i=0; i<r; i++) for (int j=0; j<c; j++) dp[i][j]=1e9;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push({0, 0, V1});
    dp[0][V1]=0;
    while (!pq.empty())
    {
        auto [w, cr, cc]=pq.top();
        pq.pop();
        if (cr!=r-1&&dp[cr+1][cc]>w+ver[cr][cc]) dp[cr+1][cc]=w+ver[cr][cc], pq.push({dp[cr+1][cc], cr+1, cc});
        if (cc!=c-1&&dp[cr][cc+1]>w+horr[cr][cc]) dp[cr][cc+1]=w+horr[cr][cc], pq.push({dp[cr][cc+1], cr, cc+1});
        if (cc!=0&&dp[cr][cc-1]>w+horl[cr][cc]) dp[cr][cc-1]=w+horl[cr][cc], pq.push({dp[cr][cc-1], cr, cc-1});
    }
    return dp[r-1][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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 12380 KB Output is correct
2 Correct 47 ms 12364 KB Output is correct
3 Correct 15747 ms 13900 KB Output is correct
4 Correct 51 ms 12376 KB Output is correct
5 Correct 43 ms 12376 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 13 ms 348 KB Output is correct
5 Correct 5 ms 576 KB Output is correct
6 Correct 6 ms 576 KB Output is correct
7 Correct 10 ms 584 KB Output is correct
8 Correct 9 ms 348 KB Output is correct
9 Correct 13 ms 568 KB Output is correct
10 Correct 9 ms 572 KB Output is correct
11 Correct 4918 ms 1336 KB Output is correct
12 Correct 17 ms 600 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 968 KB Output is correct
2 Correct 161 ms 1116 KB Output is correct
3 Correct 97 ms 856 KB Output is correct
4 Correct 94 ms 856 KB Output is correct
5 Correct 100 ms 856 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 149 ms 860 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 24152 KB Output is correct
2 Correct 901 ms 24156 KB Output is correct
3 Correct 296 ms 24156 KB Output is correct
4 Execution timed out 20035 ms 24740 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 856 KB Output is correct
2 Correct 163 ms 1112 KB Output is correct
3 Correct 95 ms 860 KB Output is correct
4 Correct 114 ms 856 KB Output is correct
5 Correct 122 ms 860 KB Output is correct
6 Correct 310 ms 24316 KB Output is correct
7 Correct 900 ms 24156 KB Output is correct
8 Correct 300 ms 24152 KB Output is correct
9 Execution timed out 20016 ms 24836 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 856 KB Output is correct
2 Correct 160 ms 1112 KB Output is correct
3 Correct 95 ms 856 KB Output is correct
4 Correct 115 ms 1104 KB Output is correct
5 Correct 94 ms 860 KB Output is correct
6 Correct 293 ms 24156 KB Output is correct
7 Correct 878 ms 24332 KB Output is correct
8 Correct 298 ms 24324 KB Output is correct
9 Execution timed out 20082 ms 24812 KB Time limit exceeded
10 Halted 0 ms 0 KB -