Submission #1152564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152564		AlgorithmWarrior	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	1095 ms	632 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

int const INF=1e9;
int const MAX=30005;
int pos[MAX];
int pas[MAX];
int n,m;

void read(){
    cin>>n>>m;
    int i;
    for(i=0;i<m;++i)
        cin>>pos[i]>>pas[i];
}

int drum[MAX];
bool ales[MAX];

int dist(int p1,int p2,int pas){
    if(p1>p2)
        swap(p1,p2);
    int dif=p2-p1;
    if(dif%pas==0)
        return dif/pas;
    return INF;
}

void dijkstra(){
    int i,j;
    for(i=1;i<=m;++i)
        drum[i]=INF;
    for(j=1;j<m;++j){
        int doge=m;
        for(i=0;i<m;++i)
            if(!ales[i] && drum[i]<drum[doge])
                doge=i;
        if(doge<m){
            ales[doge]=1;
            for(i=0;i<m;++i)
                if(drum[i]>drum[doge]+dist(pos[doge],pos[i],pas[doge]))
                    drum[i]=drum[doge]+dist(pos[doge],pos[i],pas[doge]);
        }
    }
}

void write(){
    if(drum[1]>10*m)
        drum[1]=INF;
    if(drum[1]==INF)
        cout<<-1;
    else
        cout<<drum[1];
}

int main()
{
    read();
    dijkstra();
    write();
    return 0;
}

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