oj.uz

Submission #1110721

# Submission time Handle Problem Language Result Execution time Memory
1110721 2024-11-10T09:17:08 Z nhphuc Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 191 ms 242504 KB 
#include <bits/stdc++.h>
using namespace std;

#define iii tuple<int, int, int>

const int N = 50500;
const int block = 200;

int n, m, b[N], v[N], dp[N][block + 7], ans = -1;
bool vis[N][block + 7];
vector<int> pw[N];
vector<pair<int, int>> Q[N * block];

int32_t main (){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= block + 1; ++j)
            dp[i][j] = -1;
    for (int i = 1; i <= m; ++i){
        cin >> b[i] >> v[i];
        pw[b[i]].push_back(v[i]);
        if (i == 1)
            Q[0].push_back({b[i], v[i]});
    }
    for (int D = 0; D < N * block; ++D){
        for (pair<int, int> it : Q[D]){
            int u = it.first;
            int t = it.second;
            if (dp[u][t] != -1)
                continue;
            if (vis[u][t])
                continue;
            vis[u][t] = true;
            dp[u][t] = D;
            if (u == b[2])
                ans = min((ans == -1 ? (int)1e16 : ans), D);
            if (t <= block){
                if (u - t >= 0 && dp[u - t][t] == -1)
                    Q[D + 1].push_back({u - t, t});
                if (u + t < n && dp[u + t][t] == -1)
                    Q[D + 1].push_back({u + t, t});
            }
            for (int X : pw[u]){
                if (X <= block){
                    if (u - X >= 0 && dp[u - X][X] == -1)
                        Q[D + 1].push_back({u - X, X});
                    if (u + X < n && dp[u + X][X] == -1)
                        Q[D + 1].push_back({u + X, X});
                } else {
                    for (int i = u - X; i >= 0; i -= X)
                        if (dp[i][block + 1] == -1)
                            Q[D + (u - i) / X].push_back({i, X});
                    for (int i = u + X; i < n; i += X)
                        if (dp[i][block + 1] == -1)
                            Q[D + (i - u) / X].push_back({i, X});
                }
            }
        }
    }
    cout << ans << "\n";
}

Compilation message

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 240712 KB Output is correct
2 Correct 161 ms 240476 KB Output is correct
3 Correct 161 ms 240712 KB Output is correct
4 Correct 161 ms 240540 KB Output is correct
5 Correct 161 ms 240712 KB Output is correct
6 Correct 150 ms 240712 KB Output is correct
7 Correct 155 ms 240516 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 240712 KB Output is correct
2 Correct 176 ms 240796 KB Output is correct
3 Correct 170 ms 240684 KB Output is correct
4 Correct 163 ms 240712 KB Output is correct
5 Correct 174 ms 240728 KB Output is correct
6 Correct 176 ms 240720 KB Output is correct
7 Correct 172 ms 240712 KB Output is correct
8 Correct 172 ms 240532 KB Output is correct
9 Correct 174 ms 240712 KB Output is correct
10 Correct 179 ms 240712 KB Output is correct
11 Correct 191 ms 240968 KB Output is correct
12 Correct 165 ms 240768 KB Output is correct
13 Correct 168 ms 240712 KB Output is correct
14 Correct 169 ms 240968 KB Output is correct
15 Correct 164 ms 240968 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 240712 KB Output is correct
2 Correct 162 ms 240712 KB Output is correct
3 Correct 168 ms 240712 KB Output is correct
4 Correct 167 ms 240692 KB Output is correct
5 Correct 168 ms 240688 KB Output is correct
6 Correct 170 ms 240548 KB Output is correct
7 Correct 163 ms 240688 KB Output is correct
8 Correct 153 ms 240528 KB Output is correct
9 Correct 156 ms 240712 KB Output is correct
10 Correct 150 ms 240712 KB Output is correct
11 Correct 159 ms 240968 KB Output is correct
12 Correct 152 ms 240712 KB Output is correct
13 Correct 153 ms 240716 KB Output is correct
14 Correct 154 ms 240976 KB Output is correct
15 Correct 156 ms 240968 KB Output is correct
16 Correct 153 ms 240724 KB Output is correct
17 Correct 151 ms 241496 KB Output is correct
18 Correct 154 ms 241992 KB Output is correct
19 Correct 159 ms 242504 KB Output is correct
20 Correct 157 ms 242436 KB Output is correct
21 Correct 167 ms 240968 KB Output is correct
22 Correct 174 ms 241992 KB Output is correct
23 Incorrect 180 ms 242052 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 240712 KB Output is correct
2 Correct 176 ms 240556 KB Output is correct
3 Correct 156 ms 240508 KB Output is correct
4 Correct 156 ms 240732 KB Output is correct
5 Correct 153 ms 240744 KB Output is correct
6 Correct 162 ms 240716 KB Output is correct
7 Correct 169 ms 240712 KB Output is correct
8 Correct 176 ms 240712 KB Output is correct
9 Correct 173 ms 240736 KB Output is correct
10 Correct 175 ms 240684 KB Output is correct
11 Correct 164 ms 241016 KB Output is correct
12 Correct 180 ms 240872 KB Output is correct
13 Correct 173 ms 240712 KB Output is correct
14 Correct 171 ms 240968 KB Output is correct
15 Correct 172 ms 240972 KB Output is correct
16 Correct 154 ms 240796 KB Output is correct
17 Correct 160 ms 241480 KB Output is correct
18 Correct 156 ms 242132 KB Output is correct
19 Correct 154 ms 242248 KB Output is correct
20 Correct 158 ms 242248 KB Output is correct
21 Correct 151 ms 240980 KB Output is correct
22 Correct 155 ms 241992 KB Output is correct
23 Incorrect 152 ms 241992 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 240568 KB Output is correct
2 Correct 153 ms 240712 KB Output is correct
3 Correct 154 ms 240540 KB Output is correct
4 Correct 153 ms 240652 KB Output is correct
5 Correct 154 ms 240712 KB Output is correct
6 Correct 151 ms 240516 KB Output is correct
7 Correct 152 ms 240712 KB Output is correct
8 Correct 158 ms 240712 KB Output is correct
9 Correct 156 ms 240724 KB Output is correct
10 Correct 171 ms 240612 KB Output is correct
11 Correct 176 ms 241108 KB Output is correct
12 Correct 175 ms 240712 KB Output is correct
13 Correct 175 ms 240732 KB Output is correct
14 Correct 174 ms 240852 KB Output is correct
15 Correct 177 ms 240972 KB Output is correct
16 Correct 172 ms 240712 KB Output is correct
17 Correct 191 ms 241488 KB Output is correct
18 Correct 176 ms 241976 KB Output is correct
19 Correct 166 ms 242248 KB Output is correct
20 Correct 170 ms 242248 KB Output is correct
21 Correct 174 ms 240896 KB Output is correct
22 Correct 167 ms 241976 KB Output is correct
23 Incorrect 168 ms 241928 KB Output isn't correct
24 Halted 0 ms 0 KB -