Submission #482763

#	Time	Username	Problem	Language	Result	Execution time	Memory
482763		radal	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	30 ms	36200 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const long long int N = 3e3+20,mod = 1e9+7,inf = 1e9,sq = 400;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,ll k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
int e[N][N],d[N];
int n,a[N],p[N];
inline void dij(){
    priority_queue<pll,vector<pll>,greater<pll>> pq;
    pq.push({0,a[0]});
    d[a[0]] = 0;
    while (!pq.empty()){
        pll p = pq.top();
        int y = p.Y;
        pq.pop();
        rep(i,0,n){
            if (d[i] > d[y] && d[i]-d[y] > e[y][i]){
                d[i] = d[y]+e[y][i];
                pq.push({d[i],i});
            }
        }
    }
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(e,127,sizeof e);
    memset(d,127,sizeof d);
    ll Inf = d[0];
    int m;
    cin >> n >> m;
    rep(i,0,m){
        cin >> a[i] >> p[i];
        if (i == 1) continue;
        int x = a[i];
        int t = 0;
        while (x < n){
            e[a[i]][x]  = min(e[a[i]][x],t);
            x += p[i];
            t++;
        }
        x = a[i]-p[i];
        t = 1;
        while (x >= 0){
            e[a[i]][x] = min(e[a[i]][x],t);
            t++;
            x -= p[i];
        }
    }
    dij();
    if (d[a[1]] >= Inf) cout << -1;
    else
        cout << d[a[1]];   
}

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