oj.uz

답안 #41666

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
41666 2018-02-20T11:13:47 Z repeating Jakarta Skyscrapers (APIO15_skyscraper) C++11
22 / 100
 23 ms 23160 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;
    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);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 21752 KB Output is correct
2 Correct 17 ms 21856 KB Output is correct
3 Correct 17 ms 22020 KB Output is correct
4 Correct 20 ms 22020 KB Output is correct
5 Correct 17 ms 22020 KB Output is correct
6 Correct 17 ms 22148 KB Output is correct
7 Correct 17 ms 22148 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 22148 KB Output is correct
2 Correct 18 ms 22148 KB Output is correct
3 Correct 19 ms 22148 KB Output is correct
4 Correct 17 ms 22148 KB Output is correct
5 Correct 17 ms 22148 KB Output is correct
6 Correct 18 ms 22148 KB Output is correct
7 Correct 18 ms 22148 KB Output is correct
8 Correct 18 ms 22244 KB Output is correct
9 Correct 18 ms 22244 KB Output is correct
10 Correct 19 ms 22284 KB Output is correct
11 Correct 22 ms 22404 KB Output is correct
12 Correct 17 ms 22404 KB Output is correct
13 Correct 18 ms 22404 KB Output is correct
14 Correct 20 ms 22404 KB Output is correct
15 Correct 23 ms 22404 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 22404 KB Output is correct
2 Correct 18 ms 22404 KB Output is correct
3 Correct 19 ms 22404 KB Output is correct
4 Correct 17 ms 22404 KB Output is correct
5 Correct 18 ms 22404 KB Output is correct
6 Correct 18 ms 22404 KB Output is correct
7 Correct 18 ms 22404 KB Output is correct
8 Correct 17 ms 22404 KB Output is correct
9 Correct 18 ms 22404 KB Output is correct
10 Correct 19 ms 22428 KB Output is correct
11 Correct 20 ms 22560 KB Output is correct
12 Correct 17 ms 22560 KB Output is correct
13 Correct 18 ms 22560 KB Output is correct
14 Correct 21 ms 22560 KB Output is correct
15 Correct 21 ms 22560 KB Output is correct
16 Correct 17 ms 22560 KB Output is correct
17 Correct 20 ms 22628 KB Output is correct
18 Correct 19 ms 22628 KB Output is correct
19 Correct 17 ms 22628 KB Output is correct
20 Correct 21 ms 22792 KB Output is correct
21 Correct 18 ms 22792 KB Output is correct
22 Correct 18 ms 22792 KB Output is correct
23 Incorrect 22 ms 22792 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 22792 KB Output is correct
2 Correct 18 ms 22792 KB Output is correct
3 Correct 17 ms 22792 KB Output is correct
4 Correct 17 ms 22792 KB Output is correct
5 Correct 20 ms 22792 KB Output is correct
6 Correct 19 ms 22792 KB Output is correct
7 Correct 18 ms 22792 KB Output is correct
8 Correct 18 ms 22792 KB Output is correct
9 Correct 17 ms 22792 KB Output is correct
10 Correct 22 ms 22792 KB Output is correct
11 Correct 20 ms 22872 KB Output is correct
12 Correct 18 ms 22872 KB Output is correct
13 Correct 18 ms 22872 KB Output is correct
14 Correct 20 ms 22872 KB Output is correct
15 Correct 19 ms 22872 KB Output is correct
16 Correct 18 ms 22872 KB Output is correct
17 Correct 21 ms 22872 KB Output is correct
18 Correct 18 ms 22872 KB Output is correct
19 Correct 18 ms 22872 KB Output is correct
20 Correct 20 ms 22976 KB Output is correct
21 Correct 20 ms 22976 KB Output is correct
22 Correct 20 ms 22976 KB Output is correct
23 Incorrect 19 ms 22976 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 22976 KB Output is correct
2 Correct 18 ms 22976 KB Output is correct
3 Correct 18 ms 22976 KB Output is correct
4 Correct 18 ms 22976 KB Output is correct
5 Correct 18 ms 22976 KB Output is correct
6 Correct 18 ms 22976 KB Output is correct
7 Correct 18 ms 22976 KB Output is correct
8 Correct 18 ms 22976 KB Output is correct
9 Correct 18 ms 22976 KB Output is correct
10 Correct 18 ms 22976 KB Output is correct
11 Correct 21 ms 22976 KB Output is correct
12 Correct 18 ms 22976 KB Output is correct
13 Correct 23 ms 22976 KB Output is correct
14 Correct 20 ms 22976 KB Output is correct
15 Correct 20 ms 22976 KB Output is correct
16 Correct 18 ms 22976 KB Output is correct
17 Correct 21 ms 22992 KB Output is correct
18 Correct 19 ms 22992 KB Output is correct
19 Correct 19 ms 22992 KB Output is correct
20 Correct 19 ms 23160 KB Output is correct
21 Correct 19 ms 23160 KB Output is correct
22 Correct 18 ms 23160 KB Output is correct
23 Incorrect 20 ms 23160 KB Output isn't correct
24 Halted 0 ms 0 KB -