Submission #695193

#	Time	Username	Problem	Language	Result	Execution time	Memory
695193		Farhan_HY	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	164 ms	119936 KiB

skyscraper

    #include <bits/stdc++.h>
    #define int long long
    #define float double
    #define pb push_back
    #define F first
    #define S second
    #define T int t; cin >> t; while(t--)
    #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     
    using namespace std;
    /// Benzema is the best player in the world
    const int N = 1e6 + 6;
    const int M = 2e3 + 3;
    const int mod = 1e9 + 7;
    const int inf = 1e18;
    const int dx[] = {-1, 1, 0, 0};
    const int dy[] = {0, 0, -1, 1};
    const int LOG = 28;
    int n, m;
    int p[N], dist[N];
    vector<pair<int, int>> adj[N];
    priority_queue<pair<int, int>> q;
    bool vis[N];
    int can[M][M];
    int b[N];
     
    void dij() {
        for(int i = 1; i <= n; i++) dist[i] = inf;
        q.push({0, b[1]});
        dist[b[1]] = 0;
        while(!q.empty()) {
            int u = q.top().S;
            q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for(auto x: adj[u]) {
                if (dist[x.F] > dist[u] + x.S)
                    dist[x.F] = dist[u] + x.S, q.push({-dist[x.F], x.F});
            }
        }
    }
     
    main() {
        IOS
        cin >> n >> m;
        for(int i = 1; i <= m; i++) {
            cin >> b[i] >> p[i];
            b[i]++;
            int j = b[i] - p[i], cnt = 1;
            while(j >= 1) {
                if (can[b[i]][j] == 0) can[b[i]][j] = inf;
                can[b[i]][j] = min(can[b[i]][j], cnt);
                j -= p[i];
                cnt++;
            }
            cnt = 1, j = b[i] + p[i];
            while(j <= n) {
                if (can[b[i]][j] == 0) can[b[i]][j] = inf;
                can[b[i]][j] = min(can[b[i]][j], cnt);
                cnt++;
                j += p[i];
            }
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if (can[i][j])
                    adj[i].push_back({j, can[i][j]});
        dij();
        if (dist[b[2]] == inf) dist[b[2]] = -1;
        cout << dist[b[2]];
    }

Compilation message (stderr)

skyscraper.cpp:43:5: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 |     main() {
      |     ^~~~

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