Submission #839240

#	Time	Username	Problem	Language	Result	Execution time	Memory
839240		drkarlicio2107	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	11 ms	25684 KiB

skyscraper

#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++){
      |                   ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43