oj.uz

Submission #602528

# Submission time Handle Problem Language Result Execution time Memory
602528 2022-07-23T07:33:37 Z snasibov05 Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 111 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

#define oo 1000000000000000000ll
#define int long long

signed main() {
    int n, m; cin >> n >> m;
    vector<int> b(m), p(m);
    for (int i = 0; i < m; ++i) cin >> b[i] >> p[i];

    vector<vector<int>> v(n);
    for (int i = 0; i < m; ++i) v[b[i]].push_back(i);

    vector<vector<int>> ed(m, vector<int>(m, oo));
    for (int i = 0; i < m; ++i){
        int cnt = 0;
        for (int j = b[i]; j < n; j += p[i]) {
            for (auto to : v[j]) ed[i][to] = min(ed[i][to], cnt);
            cnt++;
        }
        cnt = 0;
        for (int j = b[i]; j >= 0; j -= p[i]){
            for (auto to : v[j]) ed[i][to] = min(ed[i][to], cnt);
            cnt++;
        }
    }

    vector<int> d(m, oo); d[0] = 0;
    vector<bool> visited(m);
    for (int i = 0; i < m; ++i){
        int mn = -1;
        for (int j = 0; j < m; ++j){
            if (!visited[j] && (mn == -1 || d[mn] > d[j])) mn = j;
        }

        if (mn == -1) break;
        visited[mn] = true;
        for (int j = 0; j < m; ++j){
            if (visited[j]) continue;
            if (d[j] > d[mn] + ed[mn][j]) d[j] = d[mn] + ed[mn][j];
        }
    }

    int ans = d[1];
    if (ans == oo) ans = -1;
    cout << ans << "\n";

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 33 ms 31700 KB Output is correct
12 Correct 55 ms 31664 KB Output is correct
13 Correct 53 ms 31700 KB Output is correct
14 Correct 28 ms 31668 KB Output is correct
15 Correct 28 ms 31756 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 38 ms 31692 KB Output is correct
12 Correct 53 ms 31756 KB Output is correct
13 Correct 50 ms 31764 KB Output is correct
14 Correct 28 ms 31700 KB Output is correct
15 Correct 28 ms 31700 KB Output is correct
16 Correct 7 ms 5844 KB Output is correct
17 Correct 26 ms 25120 KB Output is correct
18 Correct 8 ms 7992 KB Output is correct
19 Correct 3 ms 2772 KB Output is correct
20 Correct 76 ms 31828 KB Output is correct
21 Correct 10 ms 11020 KB Output is correct
22 Correct 5 ms 4436 KB Output is correct
23 Correct 8 ms 7636 KB Output is correct
24 Correct 29 ms 28380 KB Output is correct
25 Correct 34 ms 31824 KB Output is correct
26 Correct 53 ms 31728 KB Output is correct
27 Correct 54 ms 31700 KB Output is correct
28 Correct 42 ms 31828 KB Output is correct
29 Correct 6 ms 4660 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 3 ms 3028 KB Output is correct
32 Correct 2 ms 2132 KB Output is correct
33 Correct 31 ms 31720 KB Output is correct
34 Correct 30 ms 31700 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 32 ms 31648 KB Output is correct
12 Correct 53 ms 31692 KB Output is correct
13 Correct 47 ms 31772 KB Output is correct
14 Correct 33 ms 31752 KB Output is correct
15 Correct 36 ms 31700 KB Output is correct
16 Correct 6 ms 5844 KB Output is correct
17 Correct 27 ms 25148 KB Output is correct
18 Correct 7 ms 8020 KB Output is correct
19 Correct 3 ms 2772 KB Output is correct
20 Correct 76 ms 31840 KB Output is correct
21 Correct 10 ms 11060 KB Output is correct
22 Correct 4 ms 4436 KB Output is correct
23 Correct 9 ms 7636 KB Output is correct
24 Correct 40 ms 28380 KB Output is correct
25 Correct 36 ms 31796 KB Output is correct
26 Correct 54 ms 31732 KB Output is correct
27 Correct 53 ms 31724 KB Output is correct
28 Correct 37 ms 31828 KB Output is correct
29 Correct 5 ms 4692 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 3 ms 2988 KB Output is correct
32 Correct 3 ms 2132 KB Output is correct
33 Correct 30 ms 31800 KB Output is correct
34 Correct 29 ms 31792 KB Output is correct
35 Runtime error 111 ms 262144 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 33 ms 31764 KB Output is correct
12 Correct 55 ms 31680 KB Output is correct
13 Correct 53 ms 31768 KB Output is correct
14 Correct 27 ms 31700 KB Output is correct
15 Correct 29 ms 31772 KB Output is correct
16 Correct 8 ms 5928 KB Output is correct
17 Correct 32 ms 25140 KB Output is correct
18 Correct 8 ms 8020 KB Output is correct
19 Correct 3 ms 2736 KB Output is correct
20 Correct 77 ms 31828 KB Output is correct
21 Correct 10 ms 11084 KB Output is correct
22 Correct 5 ms 4464 KB Output is correct
23 Correct 8 ms 7680 KB Output is correct
24 Correct 30 ms 28364 KB Output is correct
25 Correct 34 ms 31716 KB Output is correct
26 Correct 56 ms 31700 KB Output is correct
27 Correct 60 ms 31828 KB Output is correct
28 Correct 36 ms 31828 KB Output is correct
29 Correct 5 ms 4656 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 3 ms 3028 KB Output is correct
32 Correct 3 ms 2132 KB Output is correct
33 Correct 30 ms 31824 KB Output is correct
34 Correct 29 ms 31792 KB Output is correct
35 Runtime error 109 ms 262144 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -