Submission #717758

#	Time	Username	Problem	Language	Result	Execution time	Memory
717758		thimote75	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1008 ms	3644 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

vector<int> nbJumps;
vector<vector<int>> jump_count;

int main () {
    int nbSky, nbDoge;
    cin >> nbSky >> nbDoge;

    nbJumps.resize(nbSky, -1);
    jump_count.resize(nbSky);

    int sx = 0;
    int ex = 0;
    for (int idDoge = 0; idDoge < nbDoge; idDoge ++) {
        int x, p;
        cin >> x >> p;

        if (idDoge == 0) sx = x;
        if (idDoge == 1) ex = x;

        jump_count[x].push_back(p);
    }

    set<pair<int, int>> mp;
    nbJumps [sx] = 0;
    mp.insert({ 0, sx });

    while (mp.size() != 0) {
        pair<int, int> mu = * mp.begin();
        mp.erase(mu);

        int curx = mu.second;
        if (curx == ex) break ;

        for (int jump : jump_count[curx]) {
            int i = 1;
            for (int nx = curx - jump; nx >= 0; nx -= jump) {
                if (nbJumps[nx] == -1 || nbJumps[nx] > nbJumps[curx] + i) {
                    if (nbJumps[nx] != -1)
                        mp.erase({ nbJumps[nx], nx });
                    
                    nbJumps[nx] = nbJumps[curx] + i;
                    mp.insert({ nbJumps[nx], nx });
                }

                i ++;
            }
            i = 1;
            for (int nx = curx + jump; nx < nbSky; nx += jump) {
                if (nbJumps[nx] == -1 || nbJumps[nx] > nbJumps[curx] + i) {
                    if (nbJumps[nx] != -1)
                        mp.erase({ nbJumps[nx], nx });
                    
                    nbJumps[nx] = nbJumps[curx] + i;
                    mp.insert({ nbJumps[nx], nx });
                }

                i ++;
            }
        }
    }

    cout << nbJumps[ex];
}

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