oj.uz

Submission #41698

# Submission time Handle Problem Language Result Execution time Memory
41698 2018-02-20T19:03:21 Z repeating Jakarta Skyscrapers (APIO15_skyscraper) C++11
22 / 100
 124 ms 140012 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=4015;
int n,m;
int xx[MX],y[MX];
const int sq=2002;
ll dp[4205][4224];
vector<int> v[MX];
ll DP(int x,int j){
    if(x<0||x>=n)R INF;
//    cout<<x<<" "<<j<<endl;
    if(x==xx[1])R 0;
    ll &ret=dp[x][j];
    if(ret!=-1)R ret;
    ret=INF;
    for(auto i : v[x])
            {ret=min(ret,DP(x,i));}
    ret=min(ret,DP(x+j,j)+1);
    ret=min(ret,DP(x-j,j)+1);
    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 100 ms 139512 KB Output is correct
2 Correct 105 ms 139512 KB Output is correct
3 Correct 102 ms 139560 KB Output is correct
4 Correct 103 ms 139756 KB Output is correct
5 Correct 100 ms 139756 KB Output is correct
6 Correct 116 ms 139756 KB Output is correct
7 Correct 100 ms 139756 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 139756 KB Output is correct
2 Correct 100 ms 139756 KB Output is correct
3 Correct 103 ms 139756 KB Output is correct
4 Correct 101 ms 139756 KB Output is correct
5 Correct 100 ms 139808 KB Output is correct
6 Correct 107 ms 139808 KB Output is correct
7 Correct 106 ms 139808 KB Output is correct
8 Correct 102 ms 139808 KB Output is correct
9 Correct 101 ms 139808 KB Output is correct
10 Correct 113 ms 139808 KB Output is correct
11 Correct 101 ms 139868 KB Output is correct
12 Correct 106 ms 139868 KB Output is correct
13 Correct 100 ms 139876 KB Output is correct
14 Correct 102 ms 139876 KB Output is correct
15 Correct 101 ms 139876 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 139876 KB Output is correct
2 Correct 102 ms 139876 KB Output is correct
3 Correct 103 ms 139876 KB Output is correct
4 Correct 99 ms 139876 KB Output is correct
5 Correct 101 ms 139876 KB Output is correct
6 Correct 100 ms 139876 KB Output is correct
7 Correct 100 ms 139876 KB Output is correct
8 Correct 101 ms 139876 KB Output is correct
9 Correct 102 ms 139876 KB Output is correct
10 Correct 107 ms 139876 KB Output is correct
11 Correct 110 ms 139896 KB Output is correct
12 Correct 101 ms 139896 KB Output is correct
13 Correct 100 ms 139896 KB Output is correct
14 Correct 104 ms 139896 KB Output is correct
15 Correct 109 ms 139896 KB Output is correct
16 Correct 104 ms 139896 KB Output is correct
17 Correct 106 ms 139896 KB Output is correct
18 Correct 111 ms 139896 KB Output is correct
19 Correct 105 ms 139896 KB Output is correct
20 Correct 103 ms 139896 KB Output is correct
21 Correct 100 ms 139896 KB Output is correct
22 Correct 108 ms 139896 KB Output is correct
23 Incorrect 104 ms 139896 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 139896 KB Output is correct
2 Correct 106 ms 139896 KB Output is correct
3 Correct 106 ms 139896 KB Output is correct
4 Correct 103 ms 139896 KB Output is correct
5 Correct 105 ms 139896 KB Output is correct
6 Correct 106 ms 139896 KB Output is correct
7 Correct 108 ms 139896 KB Output is correct
8 Correct 113 ms 139896 KB Output is correct
9 Correct 102 ms 139896 KB Output is correct
10 Correct 114 ms 139896 KB Output is correct
11 Correct 102 ms 139992 KB Output is correct
12 Correct 101 ms 139992 KB Output is correct
13 Correct 101 ms 139992 KB Output is correct
14 Correct 106 ms 139992 KB Output is correct
15 Correct 104 ms 139992 KB Output is correct
16 Correct 100 ms 139992 KB Output is correct
17 Correct 103 ms 139992 KB Output is correct
18 Correct 104 ms 139992 KB Output is correct
19 Correct 109 ms 139992 KB Output is correct
20 Correct 124 ms 139992 KB Output is correct
21 Correct 104 ms 139992 KB Output is correct
22 Correct 116 ms 139992 KB Output is correct
23 Incorrect 106 ms 139992 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 139992 KB Output is correct
2 Correct 103 ms 139992 KB Output is correct
3 Correct 100 ms 139992 KB Output is correct
4 Correct 105 ms 139992 KB Output is correct
5 Correct 123 ms 139992 KB Output is correct
6 Correct 108 ms 139992 KB Output is correct
7 Correct 111 ms 139992 KB Output is correct
8 Correct 103 ms 139992 KB Output is correct
9 Correct 100 ms 139992 KB Output is correct
10 Correct 106 ms 139992 KB Output is correct
11 Correct 104 ms 139992 KB Output is correct
12 Correct 116 ms 139992 KB Output is correct
13 Correct 105 ms 139992 KB Output is correct
14 Correct 105 ms 139992 KB Output is correct
15 Correct 101 ms 139992 KB Output is correct
16 Correct 99 ms 139992 KB Output is correct
17 Correct 105 ms 139992 KB Output is correct
18 Correct 101 ms 139992 KB Output is correct
19 Correct 107 ms 139992 KB Output is correct
20 Correct 102 ms 140012 KB Output is correct
21 Correct 100 ms 140012 KB Output is correct
22 Correct 105 ms 140012 KB Output is correct
23 Incorrect 100 ms 140012 KB Output isn't correct
24 Halted 0 ms 0 KB -