oj.uz

Submission #548617

# Submission time Handle Problem Language Result Execution time Memory
548617 2022-04-14T02:23:19 Z joshjms Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 198120 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] * 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;
        }
        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 * 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 ();
}

Compilation message

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:38:29: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   38 |             dp[i][j] = 1e18 + 7;
      |                        ~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 127160 KB Output is correct
2 Correct 71 ms 127156 KB Output is correct
3 Correct 62 ms 127196 KB Output is correct
4 Correct 62 ms 127140 KB Output is correct
5 Correct 59 ms 127052 KB Output is correct
6 Correct 72 ms 127160 KB Output is correct
7 Correct 62 ms 127088 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 127052 KB Output is correct
2 Correct 61 ms 127120 KB Output is correct
3 Correct 64 ms 127188 KB Output is correct
4 Correct 61 ms 127052 KB Output is correct
5 Correct 69 ms 127164 KB Output is correct
6 Correct 67 ms 127064 KB Output is correct
7 Correct 64 ms 127104 KB Output is correct
8 Correct 63 ms 127172 KB Output is correct
9 Correct 64 ms 127180 KB Output is correct
10 Correct 74 ms 127192 KB Output is correct
11 Correct 64 ms 127380 KB Output is correct
12 Correct 70 ms 127152 KB Output is correct
13 Correct 61 ms 127168 KB Output is correct
14 Correct 68 ms 127364 KB Output is correct
15 Correct 67 ms 127440 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 127072 KB Output is correct
2 Correct 62 ms 127044 KB Output is correct
3 Correct 62 ms 127096 KB Output is correct
4 Correct 61 ms 127060 KB Output is correct
5 Correct 69 ms 127132 KB Output is correct
6 Correct 69 ms 127080 KB Output is correct
7 Correct 77 ms 127164 KB Output is correct
8 Correct 63 ms 127180 KB Output is correct
9 Correct 60 ms 127188 KB Output is correct
10 Correct 63 ms 127168 KB Output is correct
11 Correct 73 ms 127304 KB Output is correct
12 Correct 67 ms 127148 KB Output is correct
13 Correct 62 ms 127256 KB Output is correct
14 Correct 63 ms 127344 KB Output is correct
15 Correct 62 ms 127352 KB Output is correct
16 Correct 61 ms 127404 KB Output is correct
17 Correct 66 ms 127968 KB Output is correct
18 Correct 76 ms 128544 KB Output is correct
19 Correct 68 ms 128656 KB Output is correct
20 Correct 67 ms 128992 KB Output is correct
21 Correct 62 ms 127552 KB Output is correct
22 Correct 62 ms 128460 KB Output is correct
23 Correct 73 ms 128492 KB Output is correct
24 Correct 67 ms 128864 KB Output is correct
25 Correct 67 ms 128660 KB Output is correct
26 Correct 71 ms 128684 KB Output is correct
27 Correct 72 ms 128672 KB Output is correct
28 Correct 72 ms 128796 KB Output is correct
29 Correct 78 ms 128576 KB Output is correct
30 Correct 80 ms 128520 KB Output is correct
31 Correct 66 ms 128588 KB Output is correct
32 Correct 64 ms 128788 KB Output is correct
33 Correct 76 ms 129420 KB Output is correct
34 Correct 72 ms 129484 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 127052 KB Output is correct
2 Correct 63 ms 127052 KB Output is correct
3 Correct 72 ms 127128 KB Output is correct
4 Correct 70 ms 127144 KB Output is correct
5 Correct 65 ms 127168 KB Output is correct
6 Correct 71 ms 127052 KB Output is correct
7 Correct 65 ms 127052 KB Output is correct
8 Correct 62 ms 127140 KB Output is correct
9 Correct 68 ms 127144 KB Output is correct
10 Correct 64 ms 127172 KB Output is correct
11 Correct 60 ms 127432 KB Output is correct
12 Correct 64 ms 127140 KB Output is correct
13 Correct 74 ms 127164 KB Output is correct
14 Correct 73 ms 127436 KB Output is correct
15 Correct 69 ms 127336 KB Output is correct
16 Correct 65 ms 127436 KB Output is correct
17 Correct 62 ms 127996 KB Output is correct
18 Correct 61 ms 128588 KB Output is correct
19 Correct 66 ms 128668 KB Output is correct
20 Correct 77 ms 129068 KB Output is correct
21 Correct 64 ms 127580 KB Output is correct
22 Correct 62 ms 128584 KB Output is correct
23 Correct 62 ms 128460 KB Output is correct
24 Correct 66 ms 128896 KB Output is correct
25 Correct 76 ms 128692 KB Output is correct
26 Correct 67 ms 128672 KB Output is correct
27 Correct 64 ms 128628 KB Output is correct
28 Correct 62 ms 128828 KB Output is correct
29 Correct 81 ms 128700 KB Output is correct
30 Correct 79 ms 128544 KB Output is correct
31 Correct 73 ms 128592 KB Output is correct
32 Correct 71 ms 128724 KB Output is correct
33 Correct 77 ms 129460 KB Output is correct
34 Correct 70 ms 129484 KB Output is correct
35 Correct 86 ms 131160 KB Output is correct
36 Correct 64 ms 128560 KB Output is correct
37 Correct 84 ms 132184 KB Output is correct
38 Correct 92 ms 132776 KB Output is correct
39 Correct 82 ms 132452 KB Output is correct
40 Correct 84 ms 132676 KB Output is correct
41 Correct 92 ms 132548 KB Output is correct
42 Correct 77 ms 128896 KB Output is correct
43 Correct 66 ms 128780 KB Output is correct
44 Correct 74 ms 129384 KB Output is correct
45 Correct 115 ms 135884 KB Output is correct
46 Correct 109 ms 136092 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 127116 KB Output is correct
2 Correct 60 ms 127144 KB Output is correct
3 Correct 63 ms 127124 KB Output is correct
4 Correct 63 ms 127124 KB Output is correct
5 Correct 68 ms 127224 KB Output is correct
6 Correct 63 ms 127160 KB Output is correct
7 Correct 62 ms 127076 KB Output is correct
8 Correct 69 ms 127248 KB Output is correct
9 Correct 64 ms 127152 KB Output is correct
10 Correct 73 ms 127188 KB Output is correct
11 Correct 70 ms 127308 KB Output is correct
12 Correct 66 ms 127240 KB Output is correct
13 Correct 63 ms 127276 KB Output is correct
14 Correct 64 ms 127376 KB Output is correct
15 Correct 68 ms 127436 KB Output is correct
16 Correct 67 ms 127376 KB Output is correct
17 Correct 63 ms 128024 KB Output is correct
18 Correct 63 ms 128504 KB Output is correct
19 Correct 63 ms 128656 KB Output is correct
20 Correct 67 ms 129064 KB Output is correct
21 Correct 66 ms 127516 KB Output is correct
22 Correct 64 ms 128484 KB Output is correct
23 Correct 63 ms 128368 KB Output is correct
24 Correct 70 ms 128772 KB Output is correct
25 Correct 68 ms 128692 KB Output is correct
26 Correct 77 ms 128576 KB Output is correct
27 Correct 64 ms 128668 KB Output is correct
28 Correct 63 ms 128872 KB Output is correct
29 Correct 75 ms 128660 KB Output is correct
30 Correct 66 ms 128588 KB Output is correct
31 Correct 73 ms 128660 KB Output is correct
32 Correct 79 ms 128740 KB Output is correct
33 Correct 80 ms 129420 KB Output is correct
34 Correct 78 ms 129420 KB Output is correct
35 Correct 78 ms 131132 KB Output is correct
36 Correct 68 ms 128444 KB Output is correct
37 Correct 83 ms 132112 KB Output is correct
38 Correct 104 ms 132532 KB Output is correct
39 Correct 86 ms 132556 KB Output is correct
40 Correct 87 ms 132620 KB Output is correct
41 Correct 92 ms 132612 KB Output is correct
42 Correct 68 ms 128892 KB Output is correct
43 Correct 70 ms 128824 KB Output is correct
44 Correct 76 ms 129200 KB Output is correct
45 Correct 99 ms 135960 KB Output is correct
46 Correct 106 ms 136108 KB Output is correct
47 Correct 129 ms 146140 KB Output is correct
48 Correct 104 ms 147196 KB Output is correct
49 Correct 87 ms 148180 KB Output is correct
50 Correct 97 ms 149236 KB Output is correct
51 Correct 125 ms 153744 KB Output is correct
52 Correct 117 ms 153864 KB Output is correct
53 Correct 89 ms 150508 KB Output is correct
54 Correct 80 ms 148212 KB Output is correct
55 Correct 84 ms 148172 KB Output is correct
56 Correct 121 ms 155600 KB Output is correct
57 Correct 86 ms 152836 KB Output is correct
58 Correct 109 ms 148528 KB Output is correct
59 Correct 106 ms 148592 KB Output is correct
60 Correct 109 ms 149168 KB Output is correct
61 Correct 98 ms 149088 KB Output is correct
62 Correct 197 ms 153816 KB Output is correct
63 Correct 195 ms 184944 KB Output is correct
64 Correct 188 ms 198120 KB Output is correct
65 Correct 703 ms 196664 KB Output is correct
66 Execution timed out 1097 ms 187604 KB Time limit exceeded
67 Halted 0 ms 0 KB -