oj.uz

Submission #1028605

# Submission time Handle Problem Language Result Execution time Memory
1028605 2024-07-20T05:57:01 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 1 ms 452 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2010, M = 30010;
int n, m, b[M], p[M], dist[N];
bool mark[N], exist[N][N];


int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i ++){
        cin >> b[i] >> p[i];
        exist[b[i]][p[i]] = 1;
    }

    memset(dist, 63, sizeof dist);
    dist[b[0]] = 0;

    for (int i = 0; i < n; i ++){
        int v = -1;
        for (int j = 0; j < n; j ++)
            if (!mark[j] and (v == -1 or dist[v] > dist[j]))
                v = j;

        mark[v] = 1;
        for (int d = 1; d <= n; d ++){
            if (!exist[v][d]) continue;
            for (int i = 1; v + d * i < n; i ++)
                dist[v + d * i] = min(dist[v + d * i], dist[v] + i);
            for (int i = 1; v - d * i >= 0; i ++)
                dist[v - d * i] = min(dist[v + d * i], dist[v] + i);
        }
    }

    if (dist[b[1]] > 1e9)
        dist[b[1]] = -1;
    cout << dist[b[1]] << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 444 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 448 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 412 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 448 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 452 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 448 KB Output isn't correct
10 Halted 0 ms 0 KB -