Submission #1102568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102568		YFHHFY	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1051 ms	2472 KiB

skyscraper

#include<bits/stdc++.h>
#define tizoboz ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
#define int long long
#define itn int
#define ss set <int>
#define prq priority_queue <int>
#define endl '\n'
const ll MOD = 1e9 + 7;
#define md(x) (((x%MOD)+MOD)%MOD)
#define vi vector <int>
#define vl vector<ll>
#define str string 
#define mp make_pair
#define mata int32_t
#define sz size
#define lc id *2
#define rc lc +1
#define SZ(x)           (int)x.size()
#define mid (l+r)/2
#define cn cin
#define ct cout
#define sep " "
#define F first
#define X first
#define S second
#define Y second
using namespace std;
typedef pair <int , int> pii;
const int maxn = 3e4 + 5;
vi g[maxn];
bool use[maxn];
int dist[maxn];
int n , m;
const int inf = 1e9;
void solve(){
    cn >> n >> m;
    vi b(m) , p(m);
    for (int i = 0 ; i < maxn ; i ++) dist[i] = inf;
    for (int i = 0 ; i < m ; i ++){
        cn >> b[i] >> p[i];
        g[b[i]].pb(p[i]);
    }
    int nd = b[0];
    dist[nd] = 0;
    while (!use[b[1]] and nd != -1){
        use[nd] = 1;
        for (auto it : g[nd]){
            for (int j = 1 ; nd + j*it < n ; j++){
                dist[nd+j*it] = min (dist[nd + j*it] , dist[nd] + j);
            }
            for (int j = 1 ; nd-j*it >= 0 ; j++){
                dist[nd -j*it] = min (dist[nd -j*it] , dist[nd] + j);
            }
        }
        nd = -1;
        for (int i = 0 ; i < n ; i++){
            if (use[i]) continue;
            if (dist[i] == 1e9) continue;
            if (nd == -1 || dist[nd] > dist[i]) nd =i;
        }
    }
	if(dist[b[1]]==1e9) dist[b[1]]=-1;
	cout<<dist[b[1]];
}
mata main(){
    tizoboz;
    int tt = 1;
    // cn >> tt;
    while (tt--){
        solve();
    }
    return 0;
}

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