oj.uz

Submission #671185

# Submission time Handle Problem Language Result Execution time Memory
671185 2022-12-12T10:11:54 Z fatemetmhr Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 92 ms 52132 KB 
// fikhshal chye daram code miznm :}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 2e3 + 10;
const int maxn  = 3e4 + 10;

int a[maxn], p[maxn], per[maxn];
int last[maxn5][maxn5], dis[maxn];
vector <pair<int, int>> adj[maxn];
bool mark[maxn];


inline bool cmp(int i, int j){return a[i] < a[j];}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); 


    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> p[i];
        per[i] = i;
    }
    sort(per, per + m); // bar hasbe a

    memset(last, -1, sizeof last);

    for(int i = 0; i < m; i++){
        int id = per[i];
        int l = a[id] % p[id], ind = -1;
        if(last[p[id]][a[id] % p[id]] != -1){
            ind = last[p[id]][a[id] % p[id]];
            l = a[ind];
        }
        for(int j = l; j < min(n, a[id] + 1); j += p[id]){
            adj[a[id]].pb({j, (a[id] - j) / p[id]});
            if(ind != -1)
                adj[a[ind]].pb({j, (j - a[ind]) / p[id]});
        }
        last[p[id]][a[id] % p[id]] = id;
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < i; j++) if(last[i][j] != -1){
        int id = last[i][j];
        for(int k = a[id] + p[id]; k < n; k += p[id])
            adj[a[id]].pb({k, (k - a[id]) / p[id]});
    }

    memset(dis, -1, sizeof dis);

    dis[a[0]] = 0;

    for(int tt = 0; tt < n; tt++){
        int v = -1;
        for(int i = 0; i < n; i++) if(!mark[i] && dis[i] != -1 && (v == -1 || dis[i] < dis[v]))
            v = i;
        if(v == -1 || v == a[1])
            break;
        mark[v] = true;
        for(auto [u, w] : adj[v]) if(!mark[u] && (dis[u] == -1 || dis[v] + w < dis[u]))
            dis[u] = dis[v] + w;
    }
    cout << dis[a[1]] << endl;
}

/*
5 3
0 2
1 1
4 1
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16852 KB Output is correct
2 Correct 7 ms 16868 KB Output is correct
3 Correct 8 ms 16908 KB Output is correct
4 Correct 8 ms 16844 KB Output is correct
5 Correct 7 ms 16852 KB Output is correct
6 Correct 8 ms 16900 KB Output is correct
7 Correct 7 ms 16852 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16864 KB Output is correct
2 Correct 7 ms 16852 KB Output is correct
3 Correct 7 ms 16852 KB Output is correct
4 Correct 7 ms 16928 KB Output is correct
5 Correct 6 ms 16852 KB Output is correct
6 Correct 6 ms 16964 KB Output is correct
7 Correct 7 ms 16852 KB Output is correct
8 Correct 8 ms 16852 KB Output is correct
9 Correct 7 ms 16852 KB Output is correct
10 Correct 7 ms 16980 KB Output is correct
11 Correct 8 ms 16980 KB Output is correct
12 Correct 7 ms 16980 KB Output is correct
13 Correct 7 ms 17108 KB Output is correct
14 Correct 7 ms 16980 KB Output is correct
15 Correct 7 ms 17068 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16852 KB Output is correct
2 Correct 6 ms 16852 KB Output is correct
3 Correct 7 ms 16852 KB Output is correct
4 Correct 7 ms 16852 KB Output is correct
5 Correct 8 ms 16852 KB Output is correct
6 Correct 7 ms 16852 KB Output is correct
7 Correct 7 ms 16852 KB Output is correct
8 Correct 7 ms 16852 KB Output is correct
9 Correct 7 ms 16892 KB Output is correct
10 Correct 7 ms 16920 KB Output is correct
11 Correct 7 ms 16980 KB Output is correct
12 Correct 7 ms 16992 KB Output is correct
13 Correct 8 ms 17108 KB Output is correct
14 Correct 8 ms 16980 KB Output is correct
15 Correct 8 ms 16980 KB Output is correct
16 Correct 8 ms 16980 KB Output is correct
17 Correct 9 ms 17164 KB Output is correct
18 Correct 9 ms 16980 KB Output is correct
19 Correct 9 ms 16980 KB Output is correct
20 Correct 37 ms 31592 KB Output is correct
21 Correct 8 ms 17016 KB Output is correct
22 Correct 9 ms 16980 KB Output is correct
23 Correct 15 ms 17072 KB Output is correct
24 Correct 17 ms 17108 KB Output is correct
25 Correct 11 ms 17004 KB Output is correct
26 Correct 14 ms 17108 KB Output is correct
27 Correct 14 ms 17108 KB Output is correct
28 Correct 16 ms 17288 KB Output is correct
29 Correct 17 ms 17640 KB Output is correct
30 Correct 18 ms 17108 KB Output is correct
31 Correct 20 ms 17348 KB Output is correct
32 Correct 17 ms 17232 KB Output is correct
33 Correct 21 ms 18204 KB Output is correct
34 Correct 18 ms 18132 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16852 KB Output is correct
2 Correct 7 ms 16896 KB Output is correct
3 Correct 9 ms 16852 KB Output is correct
4 Correct 7 ms 16852 KB Output is correct
5 Correct 7 ms 16852 KB Output is correct
6 Correct 8 ms 16852 KB Output is correct
7 Correct 8 ms 16852 KB Output is correct
8 Correct 6 ms 16884 KB Output is correct
9 Correct 6 ms 16852 KB Output is correct
10 Correct 7 ms 16980 KB Output is correct
11 Correct 7 ms 16980 KB Output is correct
12 Correct 8 ms 16956 KB Output is correct
13 Correct 7 ms 17108 KB Output is correct
14 Correct 10 ms 16980 KB Output is correct
15 Correct 9 ms 16980 KB Output is correct
16 Correct 7 ms 16980 KB Output is correct
17 Correct 9 ms 17108 KB Output is correct
18 Correct 9 ms 16952 KB Output is correct
19 Correct 8 ms 16980 KB Output is correct
20 Correct 37 ms 31676 KB Output is correct
21 Correct 7 ms 16980 KB Output is correct
22 Correct 9 ms 16980 KB Output is correct
23 Correct 14 ms 16980 KB Output is correct
24 Correct 17 ms 17156 KB Output is correct
25 Correct 11 ms 17108 KB Output is correct
26 Correct 12 ms 17108 KB Output is correct
27 Correct 14 ms 17072 KB Output is correct
28 Correct 18 ms 17180 KB Output is correct
29 Correct 18 ms 17640 KB Output is correct
30 Correct 16 ms 17108 KB Output is correct
31 Correct 17 ms 17220 KB Output is correct
32 Correct 17 ms 17236 KB Output is correct
33 Correct 21 ms 18128 KB Output is correct
34 Correct 18 ms 18132 KB Output is correct
35 Correct 19 ms 18840 KB Output is correct
36 Correct 10 ms 17236 KB Output is correct
37 Correct 22 ms 19924 KB Output is correct
38 Correct 22 ms 19756 KB Output is correct
39 Correct 19 ms 19820 KB Output is correct
40 Correct 21 ms 19860 KB Output is correct
41 Correct 21 ms 19752 KB Output is correct
42 Correct 19 ms 18136 KB Output is correct
43 Correct 19 ms 18176 KB Output is correct
44 Correct 86 ms 52132 KB Output is correct
45 Correct 29 ms 22168 KB Output is correct
46 Correct 28 ms 22088 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16852 KB Output is correct
2 Correct 7 ms 16852 KB Output is correct
3 Correct 7 ms 16908 KB Output is correct
4 Correct 7 ms 16852 KB Output is correct
5 Correct 10 ms 16852 KB Output is correct
6 Correct 9 ms 16856 KB Output is correct
7 Correct 8 ms 16852 KB Output is correct
8 Correct 8 ms 16852 KB Output is correct
9 Correct 10 ms 16904 KB Output is correct
10 Correct 9 ms 16980 KB Output is correct
11 Correct 9 ms 17076 KB Output is correct
12 Correct 8 ms 16972 KB Output is correct
13 Correct 8 ms 17168 KB Output is correct
14 Correct 8 ms 16980 KB Output is correct
15 Correct 8 ms 16980 KB Output is correct
16 Correct 8 ms 16980 KB Output is correct
17 Correct 10 ms 17108 KB Output is correct
18 Correct 10 ms 16980 KB Output is correct
19 Correct 12 ms 17048 KB Output is correct
20 Correct 40 ms 31664 KB Output is correct
21 Correct 8 ms 17004 KB Output is correct
22 Correct 13 ms 17056 KB Output is correct
23 Correct 20 ms 17044 KB Output is correct
24 Correct 20 ms 17176 KB Output is correct
25 Correct 12 ms 17016 KB Output is correct
26 Correct 17 ms 17108 KB Output is correct
27 Correct 15 ms 17136 KB Output is correct
28 Correct 18 ms 17304 KB Output is correct
29 Correct 22 ms 17604 KB Output is correct
30 Correct 18 ms 17204 KB Output is correct
31 Correct 20 ms 17340 KB Output is correct
32 Correct 18 ms 17240 KB Output is correct
33 Correct 21 ms 18132 KB Output is correct
34 Correct 20 ms 18228 KB Output is correct
35 Correct 26 ms 18928 KB Output is correct
36 Correct 14 ms 17244 KB Output is correct
37 Correct 26 ms 19976 KB Output is correct
38 Correct 29 ms 19816 KB Output is correct
39 Correct 20 ms 19784 KB Output is correct
40 Correct 20 ms 19924 KB Output is correct
41 Correct 21 ms 19804 KB Output is correct
42 Correct 20 ms 18196 KB Output is correct
43 Correct 19 ms 18104 KB Output is correct
44 Correct 92 ms 52092 KB Output is correct
45 Correct 29 ms 22236 KB Output is correct
46 Correct 35 ms 22148 KB Output is correct
47 Runtime error 32 ms 34680 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -