oj.uz

Submission #548616

# Submission time Handle Problem Language Result Execution time Memory
548616 2022-04-14T02:19:56 Z joshjms Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 251736 KB 
#include <bits/stdc++.h>
using namespace std;

#define int 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] * p[i] <= n)
            doge[b[i]][p[i]] = true;
        if(p[i] * p[i] > n) {
            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 * j <= n; j++) {
            dp[i][j] = 1e18 + 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;
        }
        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}});
            }
        }
        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 * i <= n; 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 59 ms 127096 KB Output is correct
2 Correct 58 ms 127040 KB Output is correct
3 Correct 59 ms 127052 KB Output is correct
4 Correct 59 ms 127072 KB Output is correct
5 Correct 60 ms 127060 KB Output is correct
6 Correct 64 ms 127052 KB Output is correct
7 Correct 61 ms 127172 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 127164 KB Output is correct
2 Correct 60 ms 127160 KB Output is correct
3 Correct 60 ms 127144 KB Output is correct
4 Correct 60 ms 127136 KB Output is correct
5 Correct 61 ms 127112 KB Output is correct
6 Correct 63 ms 127096 KB Output is correct
7 Correct 60 ms 127120 KB Output is correct
8 Correct 60 ms 127144 KB Output is correct
9 Correct 61 ms 127180 KB Output is correct
10 Correct 60 ms 127300 KB Output is correct
11 Correct 64 ms 127532 KB Output is correct
12 Correct 63 ms 127224 KB Output is correct
13 Correct 60 ms 127288 KB Output is correct
14 Correct 62 ms 127564 KB Output is correct
15 Correct 61 ms 127608 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 127144 KB Output is correct
2 Correct 59 ms 127040 KB Output is correct
3 Correct 62 ms 127168 KB Output is correct
4 Correct 68 ms 127140 KB Output is correct
5 Correct 61 ms 127088 KB Output is correct
6 Correct 63 ms 127100 KB Output is correct
7 Correct 60 ms 127168 KB Output is correct
8 Correct 66 ms 127172 KB Output is correct
9 Correct 62 ms 127256 KB Output is correct
10 Correct 61 ms 127256 KB Output is correct
11 Correct 62 ms 127480 KB Output is correct
12 Correct 61 ms 127252 KB Output is correct
13 Correct 64 ms 127356 KB Output is correct
14 Correct 64 ms 127580 KB Output is correct
15 Correct 62 ms 127508 KB Output is correct
16 Correct 62 ms 127592 KB Output is correct
17 Correct 65 ms 128692 KB Output is correct
18 Correct 65 ms 129836 KB Output is correct
19 Correct 63 ms 130084 KB Output is correct
20 Correct 64 ms 130440 KB Output is correct
21 Correct 65 ms 128076 KB Output is correct
22 Correct 73 ms 129744 KB Output is correct
23 Correct 63 ms 129608 KB Output is correct
24 Correct 66 ms 130244 KB Output is correct
25 Correct 69 ms 130192 KB Output is correct
26 Correct 63 ms 130144 KB Output is correct
27 Correct 64 ms 130120 KB Output is correct
28 Correct 64 ms 130372 KB Output is correct
29 Correct 75 ms 130028 KB Output is correct
30 Correct 65 ms 130008 KB Output is correct
31 Correct 71 ms 130112 KB Output is correct
32 Correct 65 ms 130324 KB Output is correct
33 Correct 80 ms 131480 KB Output is correct
34 Correct 73 ms 131548 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 127132 KB Output is correct
2 Correct 61 ms 127068 KB Output is correct
3 Correct 66 ms 127164 KB Output is correct
4 Correct 62 ms 127052 KB Output is correct
5 Correct 60 ms 127172 KB Output is correct
6 Correct 61 ms 127168 KB Output is correct
7 Correct 61 ms 127052 KB Output is correct
8 Correct 59 ms 127180 KB Output is correct
9 Correct 62 ms 127256 KB Output is correct
10 Correct 61 ms 127376 KB Output is correct
11 Correct 66 ms 127452 KB Output is correct
12 Correct 70 ms 127364 KB Output is correct
13 Correct 61 ms 127264 KB Output is correct
14 Correct 63 ms 127504 KB Output is correct
15 Correct 70 ms 127544 KB Output is correct
16 Correct 65 ms 127560 KB Output is correct
17 Correct 64 ms 128716 KB Output is correct
18 Correct 63 ms 129868 KB Output is correct
19 Correct 66 ms 130080 KB Output is correct
20 Correct 65 ms 130444 KB Output is correct
21 Correct 61 ms 127776 KB Output is correct
22 Correct 68 ms 129812 KB Output is correct
23 Correct 63 ms 129660 KB Output is correct
24 Correct 63 ms 130288 KB Output is correct
25 Correct 69 ms 130264 KB Output is correct
26 Correct 63 ms 130044 KB Output is correct
27 Correct 64 ms 130052 KB Output is correct
28 Correct 64 ms 130380 KB Output is correct
29 Correct 74 ms 130096 KB Output is correct
30 Correct 65 ms 129928 KB Output is correct
31 Correct 69 ms 130164 KB Output is correct
32 Correct 73 ms 130392 KB Output is correct
33 Correct 80 ms 131564 KB Output is correct
34 Correct 69 ms 131508 KB Output is correct
35 Correct 79 ms 133268 KB Output is correct
36 Correct 66 ms 129376 KB Output is correct
37 Correct 78 ms 135540 KB Output is correct
38 Correct 93 ms 135736 KB Output is correct
39 Correct 84 ms 135648 KB Output is correct
40 Correct 85 ms 135844 KB Output is correct
41 Correct 94 ms 135880 KB Output is correct
42 Correct 67 ms 130508 KB Output is correct
43 Correct 73 ms 130556 KB Output is correct
44 Correct 67 ms 130916 KB Output is correct
45 Correct 111 ms 143016 KB Output is correct
46 Correct 92 ms 143224 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 127076 KB Output is correct
2 Correct 66 ms 127112 KB Output is correct
3 Correct 60 ms 127156 KB Output is correct
4 Correct 69 ms 127152 KB Output is correct
5 Correct 68 ms 127056 KB Output is correct
6 Correct 60 ms 127076 KB Output is correct
7 Correct 60 ms 127184 KB Output is correct
8 Correct 62 ms 127180 KB Output is correct
9 Correct 60 ms 127256 KB Output is correct
10 Correct 60 ms 127292 KB Output is correct
11 Correct 62 ms 127436 KB Output is correct
12 Correct 62 ms 127276 KB Output is correct
13 Correct 60 ms 127316 KB Output is correct
14 Correct 65 ms 127524 KB Output is correct
15 Correct 61 ms 127516 KB Output is correct
16 Correct 63 ms 127544 KB Output is correct
17 Correct 62 ms 128732 KB Output is correct
18 Correct 62 ms 129872 KB Output is correct
19 Correct 62 ms 130120 KB Output is correct
20 Correct 68 ms 130572 KB Output is correct
21 Correct 60 ms 127836 KB Output is correct
22 Correct 61 ms 129748 KB Output is correct
23 Correct 63 ms 129612 KB Output is correct
24 Correct 64 ms 130264 KB Output is correct
25 Correct 62 ms 130164 KB Output is correct
26 Correct 66 ms 130156 KB Output is correct
27 Correct 63 ms 130100 KB Output is correct
28 Correct 64 ms 130412 KB Output is correct
29 Correct 75 ms 130088 KB Output is correct
30 Correct 66 ms 130008 KB Output is correct
31 Correct 78 ms 130084 KB Output is correct
32 Correct 65 ms 130408 KB Output is correct
33 Correct 83 ms 131504 KB Output is correct
34 Correct 72 ms 131544 KB Output is correct
35 Correct 80 ms 133380 KB Output is correct
36 Correct 65 ms 129384 KB Output is correct
37 Correct 78 ms 135544 KB Output is correct
38 Correct 87 ms 135816 KB Output is correct
39 Correct 82 ms 135576 KB Output is correct
40 Correct 82 ms 135776 KB Output is correct
41 Correct 85 ms 135888 KB Output is correct
42 Correct 66 ms 130448 KB Output is correct
43 Correct 66 ms 130480 KB Output is correct
44 Correct 65 ms 130824 KB Output is correct
45 Correct 104 ms 143000 KB Output is correct
46 Correct 92 ms 143072 KB Output is correct
47 Correct 104 ms 161416 KB Output is correct
48 Correct 94 ms 165148 KB Output is correct
49 Correct 95 ms 167420 KB Output is correct
50 Correct 98 ms 169988 KB Output is correct
51 Correct 121 ms 177492 KB Output is correct
52 Correct 124 ms 177768 KB Output is correct
53 Correct 101 ms 171900 KB Output is correct
54 Correct 85 ms 169352 KB Output is correct
55 Correct 93 ms 169428 KB Output is correct
56 Correct 115 ms 176972 KB Output is correct
57 Correct 80 ms 173964 KB Output is correct
58 Correct 115 ms 169832 KB Output is correct
59 Correct 111 ms 169860 KB Output is correct
60 Correct 111 ms 170936 KB Output is correct
61 Correct 109 ms 170780 KB Output is correct
62 Correct 203 ms 178388 KB Output is correct
63 Correct 221 ms 240864 KB Output is correct
64 Correct 213 ms 251096 KB Output is correct
65 Correct 793 ms 251736 KB Output is correct
66 Execution timed out 1093 ms 235276 KB Time limit exceeded
67 Halted 0 ms 0 KB -