Submission #391318

#	Time	Username	Problem	Language	Result	Execution time	Memory
391318		Hegdahl	Toll (BOI17_toll)	C++17	100 / 100	1265 ms	6400 KiB

toll

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include <bits/stdc++.h>
#define ar array

using namespace std;
using ll = long long;

const ll INF = 1LL<<60;
const int mxN = 5e4;

ar<ll, 5> g[mxN];
int mnNxt[mxN];

ll ans[mxN+10];

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  int k, n, m, q; cin >> k >> n >> m >> q;
  cerr << k << '\n';

  for (int i = 0; i < n; ++i)
    for (int d = 0; d < k; ++d)
      g[i][d] = INF;
  for (int mm = 0; mm < m; ++mm) {
    int i, j, w; cin >> i >> j >> w;
    g[i][j%k] = w;
  }

  for (int i = 0; i < n; ++i)
    mnNxt[i] = i/k*k+k;

  fill(ans, ans+n+10, INF);

  for (int qq = 0; qq < q; ++qq) {
    int i, j; cin >> i >> j;

    for (int p = j+1; p < n; ++p)
      ans[p] = INF;

    ans[j] = 0;
    for (int p = j-1; p >= i; --p) {
      ans[p] = INF;
      for (int d = 0; d < k; ++d)
        ans[p] = min(ans[mnNxt[p]+d]+g[p][d], ans[p]);
    }

    if (ans[i] > INF/2) cout << "-1\n";
    else cout << ans[i] << '\n';
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44