Submission #985488

#	Time	Username	Problem	Language	Result	Execution time	Memory
985488		muratcepeda	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	88 ms	32592 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
#define lli long long int
#define rep(i, a, b) for(int i = a; i <= b; i++)


#define MAX 2000
#define MAXM 30000

int n, m, b[MAXM + 3], p[MAXM + 3], vis[MAX + 3][MAX + 3], opt[MAX + 3][MAX + 3], destino, res;
vector < int > v[MAX];
queue < pair < int, pair < int, int > > > q;

void salta(int largo, int pos, int salto){
    if(pos < n && pos >= 0 && !vis[pos][salto]){
        q.push({largo + 1, {pos, salto}});
        vis[pos][salto] = 1;  
        opt[pos][salto] = largo;
    }
}

int main(){

    cin >> n >> m;
    rep(i, 0, m - 1){
        cin >> b[i] >> p[i];
        v[b[i]].push_back(i);
    }
    res = -1;
    destino = b[1];
    vis[b[0]][p[0]] = 1;
    opt[b[0]][p[0]] = 0;
    q.push({0, {b[0], p[0]}});

    while(!q.empty()){
        int largo = q.front().first;
        int pos = q.front().second.first;
        int salto = q.front().second.second;
        q.pop();
        if(pos == destino){
            res = largo;
            break;
        }
        salta(largo, pos + salto, salto);
        salta(largo, pos - salto, salto);
        for(auto s: v[pos]){
            salta(largo, pos + p[s], p[s]);
            salta(largo, pos - p[s], p[s]);
        }
    }
    cout << res;

    return 0;
}

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