Submission #511276

#TimeUsernameProblemLanguageResultExecution timeMemory
511276CaoHuuKhuongDuyJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1030 ms27288 KiB
#include <bits/stdc++.h> using namespace std; const int N=3e4+9; const int oo=1e9+9; typedef pair <int,int> ii; typedef pair <int,ii> iii; int can,n,m,a[N],p[N],f[N][176]; bool First[N],check[N][176],doge[N]; vector <int> num[N]; priority_queue <iii,vector<iii>,greater<iii> > q; void update(int x,int dist,int val) { if (f[x][dist]>val) { f[x][dist]=val; q.push({val,{x,dist}}); } if (num[x].size()==0||dist==0) return; } int solve() { if (p[1]>=can) { f[a[1]][0]=0; q.push({0,{a[1],0}}); } else { f[a[1]][p[1]]=0; q.push({0,{a[1],p[1]}}); } int val,x,dist; while (!q.empty()) { val=q.top().first; x=q.top().second.first; dist=q.top().second.second; q.pop(); // cout<<x<<" "<<dist<<" "<<val<<" "<<q.size()<<endl; if (f[x][dist]!=val) continue; if (!First[x]) { First[x]=true; for (int i=0;i<can;i++) if (check[x][i]||i==0) update(x,i,val); } if (dist!=0) { if (x+dist<=n) update(x+dist,dist,f[x][dist]+1); if (x-dist>=1) update(x-dist,dist,f[x][dist]+1); } for (int xnew:num[x]) { int dem=0; for (int i=x+p[xnew];i<=n;i+=p[xnew]) { // cout<<i<<endl; dem++; update(i,0,val+dem); } dem=0; for (int i=x-p[xnew];i>=1;i-=p[xnew]) { //cout<<i<<endl; dem++; update(i,0,val+dem); } } // break; } int res=oo; for (int i=0;i<=can;i++) res=min(res,f[a[2]][i]); if (res==oo) res=-1; return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); //freopen("test.inp","r",stdin); cin>>n>>m; can=sqrt(n); for (int i=0;i<=n;i++) for (int j=0;j<=can;j++) f[i][j]=oo; for (int i=1;i<=m;i++) { cin>>a[i]>>p[i]; doge[a[i]]=true; a[i]++; if (p[i]>=can) num[a[i]].push_back(i); else check[a[i]][p[i]]=true; } cout<<solve(); return 0; }
#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...