oj.uz

Submission #386682

# Submission time Handle Problem Language Result Execution time Memory
386682 2021-04-07T08:14:24 Z wenqi Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 308 ms 78444 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 1
#define O 3069
#define MAX 969000000
#define OM (O / 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 44 ms 77548 KB Output is correct
2 Correct 46 ms 77548 KB Output is correct
3 Correct 44 ms 77608 KB Output is correct
4 Correct 47 ms 77548 KB Output is correct
5 Correct 45 ms 77548 KB Output is correct
6 Correct 46 ms 77548 KB Output is correct
7 Correct 44 ms 77548 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 77548 KB Output is correct
2 Correct 48 ms 77548 KB Output is correct
3 Correct 45 ms 77548 KB Output is correct
4 Correct 46 ms 77548 KB Output is correct
5 Correct 45 ms 77548 KB Output is correct
6 Correct 45 ms 77548 KB Output is correct
7 Correct 44 ms 77548 KB Output is correct
8 Correct 43 ms 77548 KB Output is correct
9 Correct 44 ms 77548 KB Output is correct
10 Correct 68 ms 77548 KB Output is correct
11 Correct 49 ms 77804 KB Output is correct
12 Correct 46 ms 77548 KB Output is correct
13 Correct 115 ms 77804 KB Output is correct
14 Correct 46 ms 77548 KB Output is correct
15 Correct 47 ms 77548 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 77548 KB Output is correct
2 Correct 44 ms 77548 KB Output is correct
3 Correct 44 ms 77696 KB Output is correct
4 Correct 43 ms 77548 KB Output is correct
5 Correct 44 ms 77548 KB Output is correct
6 Correct 62 ms 77548 KB Output is correct
7 Correct 57 ms 77548 KB Output is correct
8 Correct 44 ms 77548 KB Output is correct
9 Correct 58 ms 77548 KB Output is correct
10 Correct 58 ms 77548 KB Output is correct
11 Correct 47 ms 77804 KB Output is correct
12 Correct 55 ms 77548 KB Output is correct
13 Correct 126 ms 77804 KB Output is correct
14 Correct 46 ms 77548 KB Output is correct
15 Correct 45 ms 77676 KB Output is correct
16 Correct 46 ms 77548 KB Output is correct
17 Correct 47 ms 77804 KB Output is correct
18 Correct 47 ms 77548 KB Output is correct
19 Correct 45 ms 77548 KB Output is correct
20 Correct 308 ms 78316 KB Output is correct
21 Correct 45 ms 77548 KB Output is correct
22 Correct 45 ms 77548 KB Output is correct
23 Incorrect 46 ms 77676 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 77548 KB Output is correct
2 Correct 45 ms 77548 KB Output is correct
3 Correct 76 ms 77548 KB Output is correct
4 Correct 53 ms 77548 KB Output is correct
5 Correct 72 ms 77548 KB Output is correct
6 Correct 71 ms 77548 KB Output is correct
7 Correct 69 ms 77548 KB Output is correct
8 Correct 53 ms 77548 KB Output is correct
9 Correct 53 ms 77548 KB Output is correct
10 Correct 44 ms 77548 KB Output is correct
11 Correct 49 ms 77804 KB Output is correct
12 Correct 44 ms 77548 KB Output is correct
13 Correct 116 ms 77804 KB Output is correct
14 Correct 47 ms 77548 KB Output is correct
15 Correct 54 ms 77548 KB Output is correct
16 Correct 45 ms 77572 KB Output is correct
17 Correct 48 ms 77804 KB Output is correct
18 Correct 45 ms 77548 KB Output is correct
19 Correct 45 ms 77568 KB Output is correct
20 Correct 307 ms 78444 KB Output is correct
21 Correct 54 ms 77548 KB Output is correct
22 Correct 52 ms 77548 KB Output is correct
23 Incorrect 66 ms 77676 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 77548 KB Output is correct
2 Correct 44 ms 77552 KB Output is correct
3 Correct 46 ms 77516 KB Output is correct
4 Correct 49 ms 77496 KB Output is correct
5 Correct 47 ms 77548 KB Output is correct
6 Correct 45 ms 77548 KB Output is correct
7 Correct 46 ms 77548 KB Output is correct
8 Correct 44 ms 77548 KB Output is correct
9 Correct 44 ms 77548 KB Output is correct
10 Correct 44 ms 77548 KB Output is correct
11 Correct 47 ms 77804 KB Output is correct
12 Correct 44 ms 77548 KB Output is correct
13 Correct 118 ms 77912 KB Output is correct
14 Correct 46 ms 77548 KB Output is correct
15 Correct 45 ms 77548 KB Output is correct
16 Correct 46 ms 77548 KB Output is correct
17 Correct 46 ms 77804 KB Output is correct
18 Correct 45 ms 77548 KB Output is correct
19 Correct 46 ms 77548 KB Output is correct
20 Correct 304 ms 78316 KB Output is correct
21 Correct 82 ms 77548 KB Output is correct
22 Correct 44 ms 77548 KB Output is correct
23 Incorrect 44 ms 77676 KB Output isn't correct
24 Halted 0 ms 0 KB -