Submission #878448

#	Time	Username	Problem	Language	Result	Execution time	Memory
878448		nima_aryan	Toll (BOI17_toll)	C++14	10 / 100	2215 ms	6236 KiB

toll

#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 (stderr)

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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44