Submission #1265648

#TimeUsernameProblemLanguageResultExecution timeMemory
1265648witek_cppDungeon 3 (JOI21_ho_t5)C++20
0 / 100
951 ms2162688 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = (1LL<<60); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; if (!(cin >> N >> M)) return 0; vector<int> A(N); vector<int> B(N); for (int i = 0; i < N; ++i) cin >> A[i]; for (int i = 0; i < N; ++i) cin >> B[i]; for (int qi = 0; qi < M; ++qi) { int S, T; ll U; cin >> S >> T >> U; --S; --T; // zamiana na 0-index (S w [0..N], T w [0..N]) if (S == T) { cout << 0 << "\n"; continue; } // sprawdź czy któryś krok wymaga więcej energii niż U (niemożliwe) bool ok = true; ll totalNeeded = 0; for (int i = S; i < T; ++i) { if (A[i] > U) { ok = false; break; } totalNeeded += A[i]; } if (!ok) { cout << -1 << "\n"; continue; } // ograniczamy U do przydatnej wartości ll Ucap = min<ll>(U, totalNeeded); int lenPos = T - S + 1; // pozycje od S do T inclusive int E = (int)Ucap; // graf stany: id = (posIndex)*(E+1) + energy, gdzie posIndex = pos - S int states = lenPos * (E + 1); vector<ll> dist(states, INF); auto id = [&](int posIdx, int e)->int { return posIdx * (E + 1) + e; }; using pli = pair<ll,int>; priority_queue<pli, vector<pli>, greater<pli>> pq; dist[id(0,0)] = 0; pq.push({0, id(0,0)}); while (!pq.empty()) { auto [c, vid] = pq.top(); pq.pop(); if (c != dist[vid]) continue; int posIdx = vid / (E + 1); int e = vid % (E + 1); int pos = S + posIdx; // rzeczywista pozycja (0-indexed floor) if (posIdx == lenPos - 1) { // dotarliśmy do T break; } // 1) ruch dalej, jeśli mamy energię int need = A[pos]; if (e >= need) { int nposIdx = posIdx + 1; int ne = e - need; int nid = id(nposIdx, ne); if (dist[nid] > c) { dist[nid] = c; pq.push({c, nid}); } } // 2) dolewamy 1 energii w tej samej pozycji (jeśli możemy) if (pos <= N-1 && e < E) { // fontanna jest na piętrach 1..N => pos in [0..N-1] int nid = id(posIdx, e+1); ll nc = c + B[pos]; if (dist[nid] > nc) { dist[nid] = nc; pq.push({nc, nid}); } } } ll ans = INF; int targetPosIdx = lenPos - 1; for (int e = 0; e <= E; ++e) { ans = min(ans, dist[id(targetPosIdx, e)]); } if (ans >= INF/2) cout << -1 << "\n"; else cout << ans << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...