oj.uz

Submission #878446

# Submission time Handle Problem Language Result Execution time Memory
878446 2023-11-24T11:26:08 Z nima_aryan Toll (BOI17_toll) C++14
10 / 100
 2234 ms 7256 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;

    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:39:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |       for (auto& [v, t] : g[u]) {
      |                  ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 7256 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 1615 ms 5248 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 20 ms 604 KB Output is correct
8 Correct 22 ms 604 KB Output is correct
9 Correct 1137 ms 4540 KB Output is correct
10 Correct 2234 ms 6620 KB Output is correct
11 Correct 1552 ms 5436 KB Output is correct
12 Correct 2090 ms 4792 KB Output is correct
13 Correct 617 ms 6400 KB Output is correct
14 Correct 408 ms 4656 KB Output is correct
15 Correct 462 ms 3808 KB Output is correct
16 Correct 465 ms 3792 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 14 ms 7256 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -