Submission #839240

#TimeUsernameProblemLanguageResultExecution timeMemory
839240drkarlicio2107Jakarta Skyscrapers (APIO15_skyscraper)C++14
0 / 100
11 ms25684 KiB
#include <bits/stdc++.h> using namespace std; int n, m; int SQ=200; int dp [30010][210]; vector <int> pos [30010]; pair <int, int> l [30010]; int rek (int x, int p){ //cout << x << " " << p << endl; if (x==1) return 0; if (dp [x][p]!=-1) return dp [x][p]; dp [x][p]=1e9; int sol=1e9; for (int i=0; i<pos [x].size(); i++){ int po=pos [x][i]; if (po>SQ){ for (int j=x+po; j<n; j+=po){ sol=min (sol, rek (j, 0)+(j-x)/po); } for (int j=x-po; j>=0; j-=po){ sol=min (sol, rek (j, 0)+(x-j)/po); } } else { if (x-po>=0) sol=min (sol, rek (x-po, po)+1); if (x+po<n) sol=min (sol, rek (x+po, po)+1); } } if (x-p>=0) sol=min (sol, rek (x-p, p)+1); if (x+p<n) sol=min (sol, rek (x+p, p)+1); return dp [x][p]=sol; } int main(){ memset (dp, -1, sizeof dp); cin >> n >> m; for (int i=0; i<m; i++) cin >> l [i].first >> l [i].second; for (int i=0; i<m; i++) pos [l [i].first].push_back (l [i].second); int sol=rek (l [0].first, l [0].second); if (sol==1e9) cout << -1 << endl; else cout << sol << endl; }

Compilation message (stderr)

skyscraper.cpp: In function 'int rek(int, int)':
skyscraper.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i=0; i<pos [x].size(); 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...