oj.uz

Submission #41667

# Submission time Handle Problem Language Result Execution time Memory
41667 2018-02-20T11:20:32 Z repeating Jakarta Skyscrapers (APIO15_skyscraper) C++11
22 / 100
 22 ms 22508 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%Id",&x)
#define SF2(x,y) scanf("%Id%Id",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()

using namespace std;
const long long INF = 1e9;
const long long MOD = 1e9+7;
const int MX=30015;
int n,m;
int xx[MX],y[MX];
const int sq=173;
int dp[30005][sq+4];
vector<int> v[MX];
int DP(int x,int j){
    if(x<0||x>=n)R INF;
//    cout<<x<<" "<<j<<endl;
    if(x==xx[1])R 0;
    int &ret=dp[x][j];
    if(ret!=-1)R ret;
    ret=INF;
    if(j==0)
        for(auto i : v[x])
            if(i<sq){ret=min(ret,DP(x,i));}
    if(j!=0)
        ret=min(ret,DP(x+j,j)+1),ret=min(ret,DP(x-j,j)+1);
    ret=min(ret,DP(x,0));
    if(j==0)
        for(auto k : v[x]){
            if(k>=sq){
                for(int i=x,j1=0;i>=0;i-=k,j1++){
                    ret=min(ret,DP(i,0)+j1);
                }
                for(int i=x,j1=0;i<n;i+=k,j1++){
                    ret=min(ret,DP(i,0)+j1);
                }
            }

        }
//    cout<<x<<" "<<j<<" "<<ret<<endl;
    R ret;

}
int main(){
    MEM(dp,-1);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>xx[i]>>y[i];
        v[xx[i]].pb(y[i]);
    }
    if(DP(xx[0],0)==INF)cout<<-1;
    else
    cout<<DP(xx[0],0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21828 KB Output is correct
2 Correct 17 ms 21856 KB Output is correct
3 Correct 17 ms 21856 KB Output is correct
4 Correct 17 ms 21856 KB Output is correct
5 Correct 17 ms 21944 KB Output is correct
6 Correct 17 ms 21944 KB Output is correct
7 Correct 16 ms 21944 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 22016 KB Output is correct
2 Correct 18 ms 22072 KB Output is correct
3 Correct 17 ms 22072 KB Output is correct
4 Correct 17 ms 22108 KB Output is correct
5 Correct 17 ms 22108 KB Output is correct
6 Correct 18 ms 22108 KB Output is correct
7 Correct 18 ms 22108 KB Output is correct
8 Correct 17 ms 22108 KB Output is correct
9 Correct 17 ms 22108 KB Output is correct
10 Correct 18 ms 22128 KB Output is correct
11 Correct 18 ms 22128 KB Output is correct
12 Correct 18 ms 22128 KB Output is correct
13 Correct 19 ms 22128 KB Output is correct
14 Correct 18 ms 22228 KB Output is correct
15 Correct 18 ms 22228 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 22228 KB Output is correct
2 Correct 17 ms 22228 KB Output is correct
3 Correct 18 ms 22228 KB Output is correct
4 Correct 18 ms 22228 KB Output is correct
5 Correct 17 ms 22228 KB Output is correct
6 Correct 16 ms 22228 KB Output is correct
7 Correct 18 ms 22228 KB Output is correct
8 Correct 17 ms 22228 KB Output is correct
9 Correct 18 ms 22228 KB Output is correct
10 Correct 17 ms 22228 KB Output is correct
11 Correct 18 ms 22228 KB Output is correct
12 Correct 18 ms 22228 KB Output is correct
13 Correct 17 ms 22228 KB Output is correct
14 Correct 19 ms 22228 KB Output is correct
15 Correct 19 ms 22228 KB Output is correct
16 Correct 19 ms 22228 KB Output is correct
17 Correct 19 ms 22508 KB Output is correct
18 Correct 18 ms 22508 KB Output is correct
19 Correct 17 ms 22508 KB Output is correct
20 Correct 22 ms 22508 KB Output is correct
21 Correct 17 ms 22508 KB Output is correct
22 Correct 17 ms 22508 KB Output is correct
23 Incorrect 20 ms 22508 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 22508 KB Output is correct
2 Correct 18 ms 22508 KB Output is correct
3 Correct 17 ms 22508 KB Output is correct
4 Correct 19 ms 22508 KB Output is correct
5 Correct 17 ms 22508 KB Output is correct
6 Correct 17 ms 22508 KB Output is correct
7 Correct 19 ms 22508 KB Output is correct
8 Correct 17 ms 22508 KB Output is correct
9 Correct 17 ms 22508 KB Output is correct
10 Correct 18 ms 22508 KB Output is correct
11 Correct 18 ms 22508 KB Output is correct
12 Correct 19 ms 22508 KB Output is correct
13 Correct 21 ms 22508 KB Output is correct
14 Correct 19 ms 22508 KB Output is correct
15 Correct 18 ms 22508 KB Output is correct
16 Correct 17 ms 22508 KB Output is correct
17 Correct 20 ms 22508 KB Output is correct
18 Correct 18 ms 22508 KB Output is correct
19 Correct 18 ms 22508 KB Output is correct
20 Correct 19 ms 22508 KB Output is correct
21 Correct 20 ms 22508 KB Output is correct
22 Correct 17 ms 22508 KB Output is correct
23 Incorrect 21 ms 22508 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22508 KB Output is correct
2 Correct 17 ms 22508 KB Output is correct
3 Correct 17 ms 22508 KB Output is correct
4 Correct 20 ms 22508 KB Output is correct
5 Correct 19 ms 22508 KB Output is correct
6 Correct 17 ms 22508 KB Output is correct
7 Correct 17 ms 22508 KB Output is correct
8 Correct 17 ms 22508 KB Output is correct
9 Correct 17 ms 22508 KB Output is correct
10 Correct 17 ms 22508 KB Output is correct
11 Correct 18 ms 22508 KB Output is correct
12 Correct 18 ms 22508 KB Output is correct
13 Correct 18 ms 22508 KB Output is correct
14 Correct 19 ms 22508 KB Output is correct
15 Correct 19 ms 22508 KB Output is correct
16 Correct 17 ms 22508 KB Output is correct
17 Correct 21 ms 22508 KB Output is correct
18 Correct 19 ms 22508 KB Output is correct
19 Correct 17 ms 22508 KB Output is correct
20 Correct 20 ms 22508 KB Output is correct
21 Correct 18 ms 22508 KB Output is correct
22 Correct 20 ms 22508 KB Output is correct
23 Incorrect 18 ms 22508 KB Output isn't correct
24 Halted 0 ms 0 KB -