oj.uz

Submission #739447

# Submission time Handle Problem Language Result Execution time Memory
739447 2023-05-10T13:18:51 Z Mauve Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 241652 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[30001][179],s,e;
vector< edge > v[30001][177]; // 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>175)
            for(j=1 ; l+r*j<n || l-r*j>=0 ; j++){
                edge a;
                a.num=l+r*j;
                a.pwr=176;
                a.cost=j;
                if(a.num<n) v[l][176].pb(a);
                a.num=l-r*j;
                if(a.num>=0) v[l][176].pb(a);
            }
        else{
            v[l][176].pb({0,{l,r}});
        }
    }
    set<edge> q;
    memset(D,-1,sizeof(D));
    q.insert({0,{s,176}});
    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!=176){
            if(D[nmbr][176]==-1) q.insert({une,{nmbr,176}});
            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][176];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 145996 KB Output is correct
2 Correct 68 ms 145912 KB Output is correct
3 Correct 71 ms 145900 KB Output is correct
4 Correct 65 ms 145980 KB Output is correct
5 Correct 64 ms 145936 KB Output is correct
6 Correct 65 ms 146020 KB Output is correct
7 Correct 67 ms 145944 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 145980 KB Output is correct
2 Correct 64 ms 145900 KB Output is correct
3 Correct 73 ms 145988 KB Output is correct
4 Correct 67 ms 146000 KB Output is correct
5 Correct 65 ms 146000 KB Output is correct
6 Correct 68 ms 145924 KB Output is correct
7 Correct 67 ms 146000 KB Output is correct
8 Correct 66 ms 145892 KB Output is correct
9 Correct 68 ms 145952 KB Output is correct
10 Correct 69 ms 145996 KB Output is correct
11 Correct 69 ms 146124 KB Output is correct
12 Correct 67 ms 146028 KB Output is correct
13 Correct 68 ms 146080 KB Output is correct
14 Correct 69 ms 146172 KB Output is correct
15 Correct 76 ms 146124 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 146012 KB Output is correct
2 Correct 65 ms 146012 KB Output is correct
3 Correct 67 ms 145956 KB Output is correct
4 Correct 65 ms 145960 KB Output is correct
5 Correct 67 ms 145980 KB Output is correct
6 Correct 67 ms 146016 KB Output is correct
7 Correct 69 ms 145944 KB Output is correct
8 Correct 69 ms 145980 KB Output is correct
9 Correct 68 ms 146008 KB Output is correct
10 Correct 68 ms 146040 KB Output is correct
11 Correct 67 ms 146136 KB Output is correct
12 Correct 69 ms 146060 KB Output is correct
13 Correct 67 ms 146068 KB Output is correct
14 Correct 67 ms 146140 KB Output is correct
15 Correct 68 ms 146124 KB Output is correct
16 Correct 69 ms 145980 KB Output is correct
17 Correct 69 ms 146124 KB Output is correct
18 Correct 67 ms 146012 KB Output is correct
19 Correct 79 ms 145916 KB Output is correct
20 Correct 71 ms 146080 KB Output is correct
21 Correct 74 ms 145956 KB Output is correct
22 Correct 69 ms 145968 KB Output is correct
23 Correct 68 ms 145976 KB Output is correct
24 Correct 73 ms 146088 KB Output is correct
25 Correct 69 ms 146060 KB Output is correct
26 Correct 71 ms 146032 KB Output is correct
27 Correct 76 ms 146028 KB Output is correct
28 Correct 76 ms 145996 KB Output is correct
29 Correct 76 ms 146036 KB Output is correct
30 Correct 74 ms 145904 KB Output is correct
31 Correct 73 ms 146020 KB Output is correct
32 Correct 87 ms 146044 KB Output is correct
33 Correct 94 ms 146156 KB Output is correct
34 Correct 89 ms 146124 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 145928 KB Output is correct
2 Correct 66 ms 145904 KB Output is correct
3 Correct 80 ms 145996 KB Output is correct
4 Correct 73 ms 146032 KB Output is correct
5 Correct 68 ms 145996 KB Output is correct
6 Correct 65 ms 145916 KB Output is correct
7 Correct 73 ms 145956 KB Output is correct
8 Correct 66 ms 145908 KB Output is correct
9 Correct 66 ms 145924 KB Output is correct
10 Correct 71 ms 145972 KB Output is correct
11 Correct 72 ms 146076 KB Output is correct
12 Correct 67 ms 146024 KB Output is correct
13 Correct 69 ms 145968 KB Output is correct
14 Correct 76 ms 146056 KB Output is correct
15 Correct 70 ms 146288 KB Output is correct
16 Correct 85 ms 145916 KB Output is correct
17 Correct 72 ms 146124 KB Output is correct
18 Correct 70 ms 145924 KB Output is correct
19 Correct 67 ms 146028 KB Output is correct
20 Correct 68 ms 145996 KB Output is correct
21 Correct 69 ms 145976 KB Output is correct
22 Correct 67 ms 145920 KB Output is correct
23 Correct 69 ms 145928 KB Output is correct
24 Correct 71 ms 146076 KB Output is correct
25 Correct 67 ms 146000 KB Output is correct
26 Correct 68 ms 146140 KB Output is correct
27 Correct 70 ms 146132 KB Output is correct
28 Correct 76 ms 146036 KB Output is correct
29 Correct 77 ms 146072 KB Output is correct
30 Correct 69 ms 146000 KB Output is correct
31 Correct 75 ms 145996 KB Output is correct
32 Correct 74 ms 145972 KB Output is correct
33 Correct 86 ms 146184 KB Output is correct
34 Correct 90 ms 146188 KB Output is correct
35 Correct 88 ms 146768 KB Output is correct
36 Correct 72 ms 146124 KB Output is correct
37 Correct 113 ms 147768 KB Output is correct
38 Correct 111 ms 147552 KB Output is correct
39 Correct 102 ms 147496 KB Output is correct
40 Correct 111 ms 147584 KB Output is correct
41 Correct 100 ms 147556 KB Output is correct
42 Correct 70 ms 146508 KB Output is correct
43 Correct 70 ms 146436 KB Output is correct
44 Correct 73 ms 146468 KB Output is correct
45 Correct 163 ms 149708 KB Output is correct
46 Correct 170 ms 149528 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 146012 KB Output is correct
2 Correct 66 ms 146016 KB Output is correct
3 Correct 65 ms 145896 KB Output is correct
4 Correct 73 ms 145892 KB Output is correct
5 Correct 66 ms 145996 KB Output is correct
6 Correct 69 ms 145964 KB Output is correct
7 Correct 67 ms 146120 KB Output is correct
8 Correct 66 ms 145996 KB Output is correct
9 Correct 65 ms 145912 KB Output is correct
10 Correct 73 ms 145924 KB Output is correct
11 Correct 68 ms 146064 KB Output is correct
12 Correct 64 ms 145996 KB Output is correct
13 Correct 65 ms 145952 KB Output is correct
14 Correct 73 ms 146076 KB Output is correct
15 Correct 65 ms 146128 KB Output is correct
16 Correct 64 ms 146036 KB Output is correct
17 Correct 71 ms 146024 KB Output is correct
18 Correct 67 ms 146048 KB Output is correct
19 Correct 68 ms 145944 KB Output is correct
20 Correct 67 ms 146008 KB Output is correct
21 Correct 66 ms 145976 KB Output is correct
22 Correct 73 ms 145996 KB Output is correct
23 Correct 67 ms 146000 KB Output is correct
24 Correct 69 ms 146056 KB Output is correct
25 Correct 67 ms 145964 KB Output is correct
26 Correct 74 ms 145964 KB Output is correct
27 Correct 70 ms 146056 KB Output is correct
28 Correct 69 ms 146064 KB Output is correct
29 Correct 77 ms 145964 KB Output is correct
30 Correct 70 ms 146032 KB Output is correct
31 Correct 75 ms 146056 KB Output is correct
32 Correct 77 ms 145988 KB Output is correct
33 Correct 92 ms 146068 KB Output is correct
34 Correct 90 ms 146096 KB Output is correct
35 Correct 84 ms 146832 KB Output is correct
36 Correct 70 ms 146112 KB Output is correct
37 Correct 101 ms 147660 KB Output is correct
38 Correct 103 ms 147548 KB Output is correct
39 Correct 96 ms 147572 KB Output is correct
40 Correct 98 ms 147584 KB Output is correct
41 Correct 98 ms 147500 KB Output is correct
42 Correct 70 ms 146512 KB Output is correct
43 Correct 70 ms 146420 KB Output is correct
44 Correct 69 ms 146548 KB Output is correct
45 Correct 153 ms 149744 KB Output is correct
46 Correct 159 ms 149544 KB Output is correct
47 Correct 270 ms 157264 KB Output is correct
48 Correct 85 ms 147528 KB Output is correct
49 Correct 72 ms 147300 KB Output is correct
50 Correct 73 ms 147080 KB Output is correct
51 Correct 144 ms 150204 KB Output is correct
52 Correct 161 ms 150368 KB Output is correct
53 Correct 81 ms 146124 KB Output is correct
54 Correct 68 ms 146016 KB Output is correct
55 Correct 72 ms 145956 KB Output is correct
56 Correct 85 ms 146904 KB Output is correct
57 Correct 179 ms 146228 KB Output is correct
58 Correct 79 ms 146488 KB Output is correct
59 Correct 103 ms 146508 KB Output is correct
60 Correct 95 ms 146896 KB Output is correct
61 Correct 85 ms 146716 KB Output is correct
62 Correct 128 ms 149360 KB Output is correct
63 Correct 716 ms 213668 KB Output is correct
64 Correct 787 ms 221832 KB Output is correct
65 Execution timed out 1083 ms 241652 KB Time limit exceeded
66 Halted 0 ms 0 KB -