oj.uz

Submission #386670

# Submission time Handle Problem Language Result Execution time Memory
386670 2021-04-07T07:52:52 Z wenqi Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 94 ms 135916 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(x) begin(x), end(x)
#define fillc(p, t, v) fill_n((t*) p, sizeof(p) / sizeof(t), v)
#define pb push_back

#define MID 169
#define O 30069
#define MAX 969000000
#define OM (O / MID + MID + 69)

int N, M;

int B[O];
int P[O];
int TP;

vector<int> SMALL[O];
vector<int> BIG[O];

int smallc[O][MID + 69];
int bigc[O][2 * OM + 69];

int dp_small(int, int);
int dp_big(int, int);

int dp_small(int pos, int step) {
    int& ans = smallc[pos][step];
    if(ans != -2) return ans;
    ans = MAX;
    if(pos == TP) return ans = 0;
    for(int j : SMALL[pos]) {
        ans = min(ans, dp_small(B[j], P[j]));
    }
    for(int j : BIG[pos]) {
        ans = min(ans, dp_big(j, OM));
    }
    if(pos - step >= 0) {
        ans = min(ans, 1 + dp_small(pos - step, step));
    }
    if(pos + step < N) {
        ans = min(ans, 1 + dp_small(pos + step, step));
    }
    return ans;
}

int dp_big(int i, int offset) {
    int& ans = bigc[i][offset];
    if(ans != -2) return ans;
    ans = MAX;
    int pos = B[i] + (offset - OM) * P[i];
    if(pos == TP) return ans = 0;
    for(int j : SMALL[pos]) {
        ans = min(ans, dp_small(B[j], P[j]));
    }
    for(int j : BIG[pos]) {
        ans = min(ans, dp_big(j, OM));
    }
    if(pos - P[i] >= 0) {
        ans = min(ans, 1 + dp_big(i, offset - 1));
    }
    if(pos + P[i] < N) {
        ans = min(ans, 1 + dp_big(i, offset + 1));
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        cin >> B[i] >> P[i];
        if(P[i] < MID)
            SMALL[B[i]].pb(i);
        else
            BIG[B[i]].pb(i);
        if(i == 1) TP = B[i];
    }
    fillc(smallc, int, -2);
    fillc(bigc, int, -2);
    int ans;
    if(P[0] < MID) {
        ans = dp_small(B[0], P[0]);
    }else{
        ans = dp_big(0, OM);
    }
    cout << (ans == MAX ? -1 : ans) << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 135532 KB Output is correct
2 Correct 77 ms 135660 KB Output is correct
3 Correct 76 ms 135532 KB Output is correct
4 Correct 76 ms 135532 KB Output is correct
5 Correct 77 ms 135532 KB Output is correct
6 Correct 77 ms 135532 KB Output is correct
7 Correct 76 ms 135552 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 135544 KB Output is correct
2 Correct 77 ms 135532 KB Output is correct
3 Correct 87 ms 135660 KB Output is correct
4 Correct 80 ms 135552 KB Output is correct
5 Correct 76 ms 135532 KB Output is correct
6 Correct 88 ms 135532 KB Output is correct
7 Correct 77 ms 135532 KB Output is correct
8 Correct 78 ms 135612 KB Output is correct
9 Correct 78 ms 135552 KB Output is correct
10 Correct 77 ms 135680 KB Output is correct
11 Correct 84 ms 135788 KB Output is correct
12 Correct 77 ms 135660 KB Output is correct
13 Correct 77 ms 135660 KB Output is correct
14 Correct 79 ms 135660 KB Output is correct
15 Correct 87 ms 135660 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 135532 KB Output is correct
2 Correct 76 ms 135532 KB Output is correct
3 Correct 77 ms 135532 KB Output is correct
4 Correct 77 ms 135532 KB Output is correct
5 Correct 82 ms 135532 KB Output is correct
6 Correct 76 ms 135532 KB Output is correct
7 Correct 77 ms 135532 KB Output is correct
8 Correct 78 ms 135532 KB Output is correct
9 Correct 78 ms 135532 KB Output is correct
10 Correct 77 ms 135660 KB Output is correct
11 Correct 79 ms 135788 KB Output is correct
12 Correct 78 ms 135660 KB Output is correct
13 Correct 89 ms 135660 KB Output is correct
14 Correct 83 ms 135660 KB Output is correct
15 Correct 78 ms 135660 KB Output is correct
16 Correct 77 ms 135532 KB Output is correct
17 Correct 90 ms 135916 KB Output is correct
18 Correct 87 ms 135660 KB Output is correct
19 Correct 77 ms 135532 KB Output is correct
20 Correct 77 ms 135852 KB Output is correct
21 Correct 77 ms 135532 KB Output is correct
22 Correct 78 ms 135532 KB Output is correct
23 Incorrect 84 ms 135788 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 135532 KB Output is correct
2 Correct 77 ms 135532 KB Output is correct
3 Correct 77 ms 135532 KB Output is correct
4 Correct 77 ms 135532 KB Output is correct
5 Correct 90 ms 135532 KB Output is correct
6 Correct 79 ms 135680 KB Output is correct
7 Correct 77 ms 135532 KB Output is correct
8 Correct 78 ms 135532 KB Output is correct
9 Correct 77 ms 135532 KB Output is correct
10 Correct 79 ms 135660 KB Output is correct
11 Correct 78 ms 135788 KB Output is correct
12 Correct 79 ms 135660 KB Output is correct
13 Correct 77 ms 135660 KB Output is correct
14 Correct 81 ms 135660 KB Output is correct
15 Correct 77 ms 135660 KB Output is correct
16 Correct 92 ms 135532 KB Output is correct
17 Correct 87 ms 135788 KB Output is correct
18 Correct 77 ms 135660 KB Output is correct
19 Correct 94 ms 135532 KB Output is correct
20 Correct 79 ms 135788 KB Output is correct
21 Correct 78 ms 135532 KB Output is correct
22 Correct 81 ms 135532 KB Output is correct
23 Incorrect 77 ms 135660 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 135572 KB Output is correct
2 Correct 77 ms 135532 KB Output is correct
3 Correct 82 ms 135532 KB Output is correct
4 Correct 76 ms 135532 KB Output is correct
5 Correct 83 ms 135532 KB Output is correct
6 Correct 77 ms 135532 KB Output is correct
7 Correct 78 ms 135564 KB Output is correct
8 Correct 77 ms 135532 KB Output is correct
9 Correct 83 ms 135532 KB Output is correct
10 Correct 76 ms 135660 KB Output is correct
11 Correct 79 ms 135788 KB Output is correct
12 Correct 79 ms 135660 KB Output is correct
13 Correct 76 ms 135660 KB Output is correct
14 Correct 79 ms 135660 KB Output is correct
15 Correct 78 ms 135660 KB Output is correct
16 Correct 78 ms 135532 KB Output is correct
17 Correct 83 ms 135788 KB Output is correct
18 Correct 92 ms 135660 KB Output is correct
19 Correct 84 ms 135560 KB Output is correct
20 Correct 77 ms 135788 KB Output is correct
21 Correct 81 ms 135660 KB Output is correct
22 Correct 80 ms 135628 KB Output is correct
23 Incorrect 77 ms 135788 KB Output isn't correct
24 Halted 0 ms 0 KB -