Submission #1196235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196235		ezzzay	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	343 ms	327680 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
bool vis[N];
vector<pair<int,int>>v[N];
int dst[N];
int X[N];
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,p;
        cin>>x>>p;
        X[i]=x;
        p=abs(p);
        for(int j=1;j<=n;j++){
            if(x-p*j>=0)v[x].pb({x-p*j,j});
            if(x+p*j<n)v[x].pb({x+p*j,j});
        }
        
    }
    for(int i=0;i<N;i++){
        dst[i]=1e14;
    }
    dst[X[0]]=0;
    priority_queue<pair<int,int>>q;
    q.push({0,X[0]});
    while(!q.empty()){
        auto [w,a]=q.top();
        q.pop();
        w=-w;
        if(dst[a]<w)continue;
        for(auto [b,c]:v[a]){
            if(dst[b]>dst[a]+c){
                dst[b]=dst[a]+c;
                q.push({-dst[b],b});
            }
        }
    }
    if(dst[X[1]]==1e14)dst[X[1]]=-1;
    cout<<dst[X[1]];
}

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