oj.uz

Submission #739442

# Submission time Handle Problem Language Result Execution time Memory
739442 2023-05-10T13:05:08 Z Mauve Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 324 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ss second
#define ff first
#define INF 2000000000000000
#define pb push_back
#define edge pair<ll, pair<ll,ll> > // une, number ,power
#define cost first
#define num second.first
#define pwr second.second
ll n,m,l,r,i,j,ii,jj,k,x,y,D[30005][261],s,e;
vector< edge > v[30005][261]; // number , power (powergu oroi bol power = 179)
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>l>>r;
        if(i==1) s=l;
        if(i==2) e=l;
        if(r>150)
            for(j=1 ; l+r*j<n || l-r*j>=0 ; j++){
                edge a;
                a.num=l+r*j;
                a.pwr=260;
                a.cost=j;
                if(a.num<n) v[l][260].pb(a);
                a.num=l-r*j;
                if(a.num>=0) v[l][260].pb(a);
            }
        else{
            v[l][260].pb({0,{l,r}});
        }
    }
    set<edge> q;
    memset(D,-1,sizeof(D));
    q.insert({0,{s,260}});
    while(!q.empty()){
        ll une, nmbr, power;
        edge foo=*(q.begin());
        une=foo.cost;
        nmbr=foo.num;
        power=foo.pwr;
        q.erase(foo);
        if(D[nmbr][power]!=-1);
        else{
        D[nmbr][power]=une;
        for(edge no : v[nmbr][power]) if(D[no.num][no.pwr]==-1) q.insert({une+no.cost,{no.num,no.pwr}});
        if(power!=260){
            if(D[nmbr][260]==-1) q.insert({une,{nmbr,260}});
            if(nmbr+power<n && D[nmbr+power][power]==-1) q.insert({une+1,{nmbr+power,power}});
            if(nmbr-power>=0 && D[nmbr-power][power]==-1) q.insert({une+1,{nmbr-power,power}});
        }
        }
    }
    cout<<D[e][260];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 214736 KB Output is correct
2 Correct 103 ms 214780 KB Output is correct
3 Correct 102 ms 214824 KB Output is correct
4 Correct 113 ms 214736 KB Output is correct
5 Correct 100 ms 214880 KB Output is correct
6 Correct 103 ms 214856 KB Output is correct
7 Correct 115 ms 214828 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 214856 KB Output is correct
2 Correct 108 ms 214860 KB Output is correct
3 Correct 95 ms 214780 KB Output is correct
4 Correct 98 ms 214732 KB Output is correct
5 Correct 98 ms 214860 KB Output is correct
6 Correct 103 ms 214732 KB Output is correct
7 Correct 104 ms 214896 KB Output is correct
8 Correct 108 ms 214848 KB Output is correct
9 Correct 97 ms 214752 KB Output is correct
10 Correct 103 ms 214808 KB Output is correct
11 Correct 97 ms 214908 KB Output is correct
12 Correct 96 ms 214876 KB Output is correct
13 Correct 96 ms 214788 KB Output is correct
14 Correct 112 ms 214936 KB Output is correct
15 Correct 100 ms 214988 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 214836 KB Output is correct
2 Correct 97 ms 214856 KB Output is correct
3 Correct 96 ms 214820 KB Output is correct
4 Correct 96 ms 214740 KB Output is correct
5 Correct 98 ms 214820 KB Output is correct
6 Correct 101 ms 214832 KB Output is correct
7 Correct 101 ms 214792 KB Output is correct
8 Correct 98 ms 214856 KB Output is correct
9 Correct 98 ms 214808 KB Output is correct
10 Correct 101 ms 214824 KB Output is correct
11 Correct 105 ms 214956 KB Output is correct
12 Correct 100 ms 214964 KB Output is correct
13 Correct 96 ms 214860 KB Output is correct
14 Correct 96 ms 214892 KB Output is correct
15 Correct 99 ms 214916 KB Output is correct
16 Correct 99 ms 214828 KB Output is correct
17 Correct 98 ms 214992 KB Output is correct
18 Correct 101 ms 214860 KB Output is correct
19 Correct 101 ms 214860 KB Output is correct
20 Correct 98 ms 214880 KB Output is correct
21 Correct 101 ms 214772 KB Output is correct
22 Correct 99 ms 214880 KB Output is correct
23 Correct 111 ms 214836 KB Output is correct
24 Correct 104 ms 214860 KB Output is correct
25 Correct 99 ms 214856 KB Output is correct
26 Correct 102 ms 214904 KB Output is correct
27 Correct 100 ms 214968 KB Output is correct
28 Correct 102 ms 214968 KB Output is correct
29 Correct 116 ms 214888 KB Output is correct
30 Correct 100 ms 214820 KB Output is correct
31 Correct 112 ms 214908 KB Output is correct
32 Correct 116 ms 214844 KB Output is correct
33 Correct 119 ms 215024 KB Output is correct
34 Correct 121 ms 214992 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 214812 KB Output is correct
2 Correct 101 ms 214860 KB Output is correct
3 Correct 99 ms 214860 KB Output is correct
4 Correct 97 ms 214820 KB Output is correct
5 Correct 111 ms 214796 KB Output is correct
6 Correct 98 ms 214832 KB Output is correct
7 Correct 96 ms 214808 KB Output is correct
8 Correct 99 ms 214812 KB Output is correct
9 Correct 95 ms 214820 KB Output is correct
10 Correct 97 ms 214776 KB Output is correct
11 Correct 102 ms 214916 KB Output is correct
12 Correct 99 ms 214800 KB Output is correct
13 Correct 97 ms 214860 KB Output is correct
14 Correct 110 ms 214952 KB Output is correct
15 Correct 107 ms 215004 KB Output is correct
16 Correct 110 ms 214812 KB Output is correct
17 Correct 100 ms 214988 KB Output is correct
18 Correct 99 ms 214860 KB Output is correct
19 Correct 106 ms 214772 KB Output is correct
20 Correct 97 ms 214860 KB Output is correct
21 Correct 100 ms 214860 KB Output is correct
22 Correct 100 ms 214880 KB Output is correct
23 Correct 108 ms 214896 KB Output is correct
24 Correct 99 ms 214964 KB Output is correct
25 Correct 98 ms 214868 KB Output is correct
26 Correct 99 ms 214868 KB Output is correct
27 Correct 100 ms 214832 KB Output is correct
28 Correct 102 ms 214868 KB Output is correct
29 Correct 107 ms 214940 KB Output is correct
30 Correct 101 ms 214812 KB Output is correct
31 Correct 106 ms 214888 KB Output is correct
32 Correct 102 ms 214980 KB Output is correct
33 Correct 116 ms 214928 KB Output is correct
34 Correct 114 ms 214924 KB Output is correct
35 Correct 113 ms 215864 KB Output is correct
36 Correct 104 ms 214936 KB Output is correct
37 Correct 136 ms 216616 KB Output is correct
38 Correct 131 ms 216560 KB Output is correct
39 Correct 128 ms 216432 KB Output is correct
40 Correct 134 ms 216540 KB Output is correct
41 Correct 135 ms 216520 KB Output is correct
42 Correct 108 ms 215280 KB Output is correct
43 Correct 106 ms 215288 KB Output is correct
44 Correct 100 ms 215240 KB Output is correct
45 Correct 183 ms 218784 KB Output is correct
46 Correct 183 ms 218528 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 214964 KB Output is correct
2 Correct 101 ms 214796 KB Output is correct
3 Correct 100 ms 214828 KB Output is correct
4 Correct 95 ms 214852 KB Output is correct
5 Correct 96 ms 214808 KB Output is correct
6 Correct 110 ms 214844 KB Output is correct
7 Correct 100 ms 214784 KB Output is correct
8 Correct 96 ms 214768 KB Output is correct
9 Correct 109 ms 214784 KB Output is correct
10 Correct 97 ms 214876 KB Output is correct
11 Correct 109 ms 214900 KB Output is correct
12 Correct 124 ms 214860 KB Output is correct
13 Correct 127 ms 214888 KB Output is correct
14 Correct 125 ms 214964 KB Output is correct
15 Correct 104 ms 214928 KB Output is correct
16 Correct 108 ms 214904 KB Output is correct
17 Correct 103 ms 214972 KB Output is correct
18 Correct 111 ms 214896 KB Output is correct
19 Correct 108 ms 214812 KB Output is correct
20 Correct 110 ms 214940 KB Output is correct
21 Correct 114 ms 214844 KB Output is correct
22 Correct 102 ms 214872 KB Output is correct
23 Correct 119 ms 214804 KB Output is correct
24 Correct 108 ms 214908 KB Output is correct
25 Correct 105 ms 214944 KB Output is correct
26 Correct 105 ms 214904 KB Output is correct
27 Correct 116 ms 214932 KB Output is correct
28 Correct 104 ms 214940 KB Output is correct
29 Correct 114 ms 214932 KB Output is correct
30 Correct 105 ms 214756 KB Output is correct
31 Correct 108 ms 214916 KB Output is correct
32 Correct 103 ms 214860 KB Output is correct
33 Correct 119 ms 215024 KB Output is correct
34 Correct 126 ms 215040 KB Output is correct
35 Correct 119 ms 215848 KB Output is correct
36 Correct 109 ms 215024 KB Output is correct
37 Correct 133 ms 216844 KB Output is correct
38 Correct 141 ms 216708 KB Output is correct
39 Correct 140 ms 216628 KB Output is correct
40 Correct 147 ms 216600 KB Output is correct
41 Correct 136 ms 216592 KB Output is correct
42 Correct 105 ms 215448 KB Output is correct
43 Correct 106 ms 215460 KB Output is correct
44 Correct 121 ms 215444 KB Output is correct
45 Correct 187 ms 218792 KB Output is correct
46 Correct 190 ms 218780 KB Output is correct
47 Correct 324 ms 226892 KB Output is correct
48 Correct 113 ms 216652 KB Output is correct
49 Correct 112 ms 216332 KB Output is correct
50 Correct 108 ms 216004 KB Output is correct
51 Correct 174 ms 219296 KB Output is correct
52 Correct 180 ms 219336 KB Output is correct
53 Correct 127 ms 215108 KB Output is correct
54 Correct 108 ms 214844 KB Output is correct
55 Correct 105 ms 214860 KB Output is correct
56 Correct 117 ms 215820 KB Output is correct
57 Correct 229 ms 215008 KB Output is correct
58 Correct 118 ms 215368 KB Output is correct
59 Correct 119 ms 215468 KB Output is correct
60 Correct 146 ms 215956 KB Output is correct
61 Correct 121 ms 215732 KB Output is correct
62 Correct 158 ms 218396 KB Output is correct
63 Runtime error 216 ms 262144 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -