oj.uz

Submission #548622

# Submission time Handle Problem Language Result Execution time Memory
548622 2022-04-14T02:30:42 Z joshjms Jakarta Skyscrapers (APIO15_skyscraper) C++14
100 / 100
 892 ms 208464 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";

const int mod = 1e9 + 7;

int n, m, b[30005], p[30005];
vector <pair<pair<int,int>,int>> g[30005][180];
int dp[30005][180];
bool doge[30005][180];

priority_queue <pair<int,pair<int,int>>> pq;
map <pair<int,int>,bool> mp;

void solve () {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> b[i] >> p[i];
        if(mp[{b[i], p[i]}]) continue;
        mp[{b[i], p[i]}] = true;
        if(p[i] <= 100)
            doge[b[i]][p[i]] = true;
        if(p[i] > 100) {
            for(int j = b[i] - p[i], c = 1; j >= 0; j -= p[i], c++)
                g[b[i]][0].pb({{j, 0}, c});
            for(int j = b[i] + p[i], c = 1; j < n; j += p[i], c++)
                g[b[i]][0].pb({{j, 0}, c});
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= 100; j++) {
            dp[i][j] = 1e9 + 7;
        }
    }
    dp[b[0]][0] = 0;
    pq.push({0, {b[0], 0}});
    while(!pq.empty()) {
        int cost = -pq.top().fi;
        int pos = pq.top().se.fi;
        int pow = pq.top().se.se;
        pq.pop();
        if(cost > dp[pos][pow]) continue;
        if(pos == b[1]) {
            cout << cost << "\n";
            return;
        }
        if(pow == 0) {
            for(auto c : g[pos][pow]) {
                if(dp[c.fi.fi][c.fi.se] > cost + c.se) {
                    dp[c.fi.fi][c.fi.se] = cost + c.se;
                    pq.push({-dp[c.fi.fi][c.fi.se], {c.fi.fi, c.fi.se}});
                }
            }
        }
        else {
            if(pos + pow < n) {
                if(dp[pos + pow][pow] > cost + 1) {
                    dp[pos + pow][pow] = cost + 1;
                    pq.push({-dp[pos + pow][pow], {pos + pow, pow}});
                }
            }
            if(pos - pow >= 0) {
                if(dp[pos - pow][pow] > cost + 1) {
                    dp[pos - pow][pow] = cost + 1;
                    pq.push({-dp[pos - pow][pow], {pos - pow, pow}});
                }
            }
        }
        for(int i = 0; i <= 100; i++) {
            if(i == pow) continue;
            if(i == 0 || doge[pos][i] == true) {
                if(dp[pos][i] > cost) {
                    dp[pos][i] = cost;
                    pq.push({-dp[pos][i], {pos, i}});
                }
            }
        }
    }
    // for(int i = 0; i < n; i++) {
    //     for(int j = 0; j * j <= n; j++) {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    cout << -1 << "\n";
}

signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve ();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 127136 KB Output is correct
2 Correct 62 ms 127064 KB Output is correct
3 Correct 58 ms 127076 KB Output is correct
4 Correct 59 ms 127052 KB Output is correct
5 Correct 58 ms 127084 KB Output is correct
6 Correct 61 ms 127164 KB Output is correct
7 Correct 61 ms 127168 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 127160 KB Output is correct
2 Correct 63 ms 127164 KB Output is correct
3 Correct 61 ms 127128 KB Output is correct
4 Correct 61 ms 127160 KB Output is correct
5 Correct 60 ms 127120 KB Output is correct
6 Correct 63 ms 127052 KB Output is correct
7 Correct 66 ms 127092 KB Output is correct
8 Correct 63 ms 127156 KB Output is correct
9 Correct 61 ms 127196 KB Output is correct
10 Correct 64 ms 127192 KB Output is correct
11 Correct 66 ms 127384 KB Output is correct
12 Correct 77 ms 127148 KB Output is correct
13 Correct 63 ms 127268 KB Output is correct
14 Correct 63 ms 127312 KB Output is correct
15 Correct 62 ms 127420 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 127160 KB Output is correct
2 Correct 64 ms 127160 KB Output is correct
3 Correct 63 ms 127052 KB Output is correct
4 Correct 61 ms 127164 KB Output is correct
5 Correct 61 ms 127216 KB Output is correct
6 Correct 68 ms 127136 KB Output is correct
7 Correct 62 ms 127220 KB Output is correct
8 Correct 66 ms 127180 KB Output is correct
9 Correct 63 ms 127144 KB Output is correct
10 Correct 58 ms 127180 KB Output is correct
11 Correct 63 ms 127308 KB Output is correct
12 Correct 64 ms 127248 KB Output is correct
13 Correct 65 ms 127216 KB Output is correct
14 Correct 64 ms 127436 KB Output is correct
15 Correct 65 ms 127364 KB Output is correct
16 Correct 63 ms 127340 KB Output is correct
17 Correct 66 ms 127916 KB Output is correct
18 Correct 63 ms 128584 KB Output is correct
19 Correct 72 ms 128800 KB Output is correct
20 Correct 65 ms 129072 KB Output is correct
21 Correct 64 ms 127468 KB Output is correct
22 Correct 65 ms 128500 KB Output is correct
23 Correct 64 ms 128520 KB Output is correct
24 Correct 67 ms 128956 KB Output is correct
25 Correct 68 ms 128728 KB Output is correct
26 Correct 64 ms 128676 KB Output is correct
27 Correct 67 ms 128596 KB Output is correct
28 Correct 64 ms 128776 KB Output is correct
29 Correct 75 ms 128784 KB Output is correct
30 Correct 69 ms 128492 KB Output is correct
31 Correct 84 ms 128636 KB Output is correct
32 Correct 83 ms 128588 KB Output is correct
33 Correct 92 ms 128684 KB Output is correct
34 Correct 76 ms 128724 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 127140 KB Output is correct
2 Correct 75 ms 127052 KB Output is correct
3 Correct 59 ms 127156 KB Output is correct
4 Correct 60 ms 127140 KB Output is correct
5 Correct 61 ms 127044 KB Output is correct
6 Correct 60 ms 127172 KB Output is correct
7 Correct 66 ms 127052 KB Output is correct
8 Correct 62 ms 127192 KB Output is correct
9 Correct 59 ms 127180 KB Output is correct
10 Correct 60 ms 127216 KB Output is correct
11 Correct 70 ms 127348 KB Output is correct
12 Correct 63 ms 127264 KB Output is correct
13 Correct 64 ms 127292 KB Output is correct
14 Correct 65 ms 127432 KB Output is correct
15 Correct 63 ms 127308 KB Output is correct
16 Correct 63 ms 127344 KB Output is correct
17 Correct 64 ms 127948 KB Output is correct
18 Correct 60 ms 128668 KB Output is correct
19 Correct 61 ms 128700 KB Output is correct
20 Correct 68 ms 129080 KB Output is correct
21 Correct 65 ms 127588 KB Output is correct
22 Correct 64 ms 128576 KB Output is correct
23 Correct 62 ms 128460 KB Output is correct
24 Correct 65 ms 129040 KB Output is correct
25 Correct 64 ms 128744 KB Output is correct
26 Correct 62 ms 128752 KB Output is correct
27 Correct 62 ms 128664 KB Output is correct
28 Correct 63 ms 128844 KB Output is correct
29 Correct 80 ms 128612 KB Output is correct
30 Correct 65 ms 128588 KB Output is correct
31 Correct 71 ms 128652 KB Output is correct
32 Correct 68 ms 128636 KB Output is correct
33 Correct 88 ms 128780 KB Output is correct
34 Correct 76 ms 128776 KB Output is correct
35 Correct 79 ms 130968 KB Output is correct
36 Correct 63 ms 128460 KB Output is correct
37 Correct 76 ms 131568 KB Output is correct
38 Correct 85 ms 132256 KB Output is correct
39 Correct 82 ms 132164 KB Output is correct
40 Correct 82 ms 132176 KB Output is correct
41 Correct 83 ms 132172 KB Output is correct
42 Correct 66 ms 128944 KB Output is correct
43 Correct 78 ms 128836 KB Output is correct
44 Correct 66 ms 129272 KB Output is correct
45 Correct 128 ms 134808 KB Output is correct
46 Correct 98 ms 134776 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 127120 KB Output is correct
2 Correct 64 ms 127160 KB Output is correct
3 Correct 60 ms 127164 KB Output is correct
4 Correct 59 ms 127104 KB Output is correct
5 Correct 68 ms 127136 KB Output is correct
6 Correct 61 ms 127204 KB Output is correct
7 Correct 65 ms 127164 KB Output is correct
8 Correct 64 ms 127180 KB Output is correct
9 Correct 60 ms 127160 KB Output is correct
10 Correct 60 ms 127192 KB Output is correct
11 Correct 60 ms 127352 KB Output is correct
12 Correct 60 ms 127228 KB Output is correct
13 Correct 61 ms 127232 KB Output is correct
14 Correct 63 ms 127436 KB Output is correct
15 Correct 65 ms 127440 KB Output is correct
16 Correct 59 ms 127404 KB Output is correct
17 Correct 61 ms 127968 KB Output is correct
18 Correct 61 ms 128668 KB Output is correct
19 Correct 62 ms 128844 KB Output is correct
20 Correct 64 ms 128968 KB Output is correct
21 Correct 62 ms 127604 KB Output is correct
22 Correct 61 ms 128588 KB Output is correct
23 Correct 66 ms 128556 KB Output is correct
24 Correct 63 ms 128968 KB Output is correct
25 Correct 65 ms 128740 KB Output is correct
26 Correct 60 ms 128716 KB Output is correct
27 Correct 62 ms 128672 KB Output is correct
28 Correct 64 ms 128848 KB Output is correct
29 Correct 74 ms 128588 KB Output is correct
30 Correct 66 ms 128520 KB Output is correct
31 Correct 68 ms 128544 KB Output is correct
32 Correct 68 ms 128588 KB Output is correct
33 Correct 90 ms 128836 KB Output is correct
34 Correct 83 ms 128680 KB Output is correct
35 Correct 78 ms 130892 KB Output is correct
36 Correct 63 ms 128488 KB Output is correct
37 Correct 73 ms 131584 KB Output is correct
38 Correct 83 ms 132208 KB Output is correct
39 Correct 81 ms 132048 KB Output is correct
40 Correct 96 ms 132136 KB Output is correct
41 Correct 84 ms 132204 KB Output is correct
42 Correct 66 ms 128908 KB Output is correct
43 Correct 67 ms 128844 KB Output is correct
44 Correct 67 ms 129276 KB Output is correct
45 Correct 131 ms 134828 KB Output is correct
46 Correct 94 ms 134752 KB Output is correct
47 Correct 106 ms 146260 KB Output is correct
48 Correct 87 ms 147192 KB Output is correct
49 Correct 85 ms 148204 KB Output is correct
50 Correct 82 ms 149220 KB Output is correct
51 Correct 108 ms 153712 KB Output is correct
52 Correct 114 ms 153872 KB Output is correct
53 Correct 89 ms 150476 KB Output is correct
54 Correct 78 ms 148288 KB Output is correct
55 Correct 87 ms 148300 KB Output is correct
56 Correct 98 ms 155656 KB Output is correct
57 Correct 71 ms 152876 KB Output is correct
58 Correct 90 ms 148484 KB Output is correct
59 Correct 91 ms 148556 KB Output is correct
60 Correct 90 ms 149144 KB Output is correct
61 Correct 92 ms 149068 KB Output is correct
62 Correct 146 ms 154340 KB Output is correct
63 Correct 162 ms 184776 KB Output is correct
64 Correct 181 ms 198220 KB Output is correct
65 Correct 221 ms 207604 KB Output is correct
66 Correct 892 ms 208464 KB Output is correct
67 Correct 373 ms 208388 KB Output is correct