Submission #671185

#	Time	Username	Problem	Language	Result	Execution time	Memory
671185		fatemetmhr	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	92 ms	52132 KiB

skyscraper

// fikhshal chye daram code miznm :}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 2e3 + 10;
const int maxn  = 3e4 + 10;

int a[maxn], p[maxn], per[maxn];
int last[maxn5][maxn5], dis[maxn];
vector <pair<int, int>> adj[maxn];
bool mark[maxn];


inline bool cmp(int i, int j){return a[i] < a[j];}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); 


    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> p[i];
        per[i] = i;
    }
    sort(per, per + m); // bar hasbe a

    memset(last, -1, sizeof last);

    for(int i = 0; i < m; i++){
        int id = per[i];
        int l = a[id] % p[id], ind = -1;
        if(last[p[id]][a[id] % p[id]] != -1){
            ind = last[p[id]][a[id] % p[id]];
            l = a[ind];
        }
        for(int j = l; j < min(n, a[id] + 1); j += p[id]){
            adj[a[id]].pb({j, (a[id] - j) / p[id]});
            if(ind != -1)
                adj[a[ind]].pb({j, (j - a[ind]) / p[id]});
        }
        last[p[id]][a[id] % p[id]] = id;
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < i; j++) if(last[i][j] != -1){
        int id = last[i][j];
        for(int k = a[id] + p[id]; k < n; k += p[id])
            adj[a[id]].pb({k, (k - a[id]) / p[id]});
    }

    memset(dis, -1, sizeof dis);

    dis[a[0]] = 0;

    for(int tt = 0; tt < n; tt++){
        int v = -1;
        for(int i = 0; i < n; i++) if(!mark[i] && dis[i] != -1 && (v == -1 || dis[i] < dis[v]))
            v = i;
        if(v == -1 || v == a[1])
            break;
        mark[v] = true;
        for(auto [u, w] : adj[v]) if(!mark[u] && (dis[u] == -1 || dis[v] + w < dis[u]))
            dis[u] = dis[v] + w;
    }
    cout << dis[a[1]] << endl;
}

/*
5 3
0 2
1 1
4 1
*/

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