Submission #23596

#TimeUsernameProblemLanguageResultExecution timeMemory
23596repeatingJakarta Skyscrapers (APIO15_skyscraper)C++11
10 / 100
3 ms6512 KiB
#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 pll pair<ll,ll> #define SF(x) scanf("%I64d",&x) using namespace std; const long long INF = 2e9; long long MOD = 1e9+7; ll n,m; ll a[2222],b[2222]; ll dp[300005]; vector<ll> adj[30005]; ll pos; stack<ll> s; ll DP(ll x){ if(x<0||x>=m)R INF; if(x==pos)R 0; ll &ret=dp[x]; if(ret!=-1)R ret; ret=INF; ll d; for(int i=0;i<adj[x].SI;i++){ d=adj[x][i]; for(int j=x+d,q=1;j<m;q++,j+=d){ret=min(ret,DP(j)+q);} for(int j=x-d,q=1;j>=0;q++,j-=d){ret=min(ret,DP(j)+q);} } for(int i=0;i<adj[x].SI;i++){ d=adj[x][i]; for(int j=x+d,q=1;j<m;q++,j+=d){ret=min(ret,DP(j)+q);} for(int j=x-d,q=1;j>=0;q++,j-=d){ret=min(ret,DP(j)+q);} } R ret; } map<ll,bool> M[30005]; int main(){ MEM(dp,-1); cin>>m>>n; for(int i=0;i<n;i++){ cin>>a[i]>>b[i]; if(M[a[i]][b[i]])C; M[a[i]][b[i]]=1; adj[a[i]].pb(b[i]); } pos=a[1]; if(DP(0)==INF)cout<<-1; else cout<<DP(a[0]); }

Compilation message (stderr)

skyscraper.cpp: In function 'long long int DP(long long int)':
skyscraper.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[x].SI;i++){
                  ^
skyscraper.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[x].SI;i++){
                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...