oj.uz

Submission #878448

# Submission time Handle Problem Language Result Execution time Memory
878448 2023-11-24T11:27:32 Z nima_aryan Toll (BOI17_toll) C++14
10 / 100
 2215 ms 6236 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr int inf = 1E9;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int K, N, M, O;
  cin >> K >> N >> M >> O;

  vector<vector<pair<int, int>>> g(N);
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    int t;
    cin >> t;
    g[b].emplace_back(a, t);
  }

  while (O--) {
    int a, b;
    cin >> a >> b;

    if (a > b) {
      cout << -1 << "\n";
      continue;
    }

    vector<int> d(b - a + 1, inf);
    d[0] = 0;

    for (int u = a + 1; u <= b; ++u) {
      for (auto& [v, t] : g[u]) {
        if (v - a >= 0) {
          d[u - a] = min(d[u], d[v - a] + t);
        }
      }
    }

    cout << (d.back() < inf ? d.back() : -1) << "\n";
  }

  return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:44:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |       for (auto& [v, t] : g[u]) {
      |                  ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 6236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1668 ms 3664 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 600 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 20 ms 604 KB Output is correct
8 Correct 22 ms 604 KB Output is correct
9 Correct 1171 ms 3392 KB Output is correct
10 Correct 2215 ms 4536 KB Output is correct
11 Correct 1688 ms 3408 KB Output is correct
12 Correct 2068 ms 3520 KB Output is correct
13 Correct 620 ms 4032 KB Output is correct
14 Correct 407 ms 2908 KB Output is correct
15 Correct 439 ms 2600 KB Output is correct
16 Correct 440 ms 2396 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 6236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -