Submission #1265650

#TimeUsernameProblemLanguageResultExecution timeMemory
1265650witek_cppDungeon 3 (JOI21_ho_t5)C++20
0 / 100
4161 ms1699188 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; // zero-based floors: 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 (nie warto trzymać większego stanu energii) ll Ucap = min<ll>(U, totalNeeded); int lenPos = T - S + 1; // pozycje od S do T inclusive // użyjemy map dla każdego pos: energy -> bestCost vector<unordered_map<int, ll>> dist(lenPos); // priorty queue: (cost, posIdx, energy) using tpl = tuple<ll,int,int>; priority_queue<tpl, vector<tpl>, greater<tpl>> pq; dist[0][0] = 0; pq.push({0, 0, 0}); ll answer = INF; while (!pq.empty()) { auto [cost, posIdx, e] = pq.top(); pq.pop(); // jeśli ten stan nie jest aktualny, pomiń auto it = dist[posIdx].find(e); if (it == dist[posIdx].end() || it->second != cost) continue; // jeśli doszliśmy do celu if (posIdx == lenPos - 1) { answer = cost; break; // Dijkstra: pierwsze dotarcie do celu ma minimalny koszt } int pos = S + posIdx; // rzeczywista pozycja (0-indexed floor) // 1) ruch dalej, jeśli mamy energię i jeśli move jest legalny (pos <= N-1) if (pos <= N-1) { int need = A[pos]; if (e >= need) { int npos = posIdx + 1; int ne = e - need; ll nc = cost; auto it2 = dist[npos].find(ne); if (it2 == dist[npos].end() || nc < it2->second) { dist[npos][ne] = nc; pq.push({nc, npos, ne}); } } } // 2) dolewamy 1 energii w tej samej pozycji (jeśli możemy i jeśli fontanna istnieje) if (pos <= N-1 && e < Ucap) { int ne = e + 1; ll nc = cost + B[pos]; auto it2 = dist[posIdx].find(ne); if (it2 == dist[posIdx].end() || nc < it2->second) { dist[posIdx][ne] = nc; pq.push({nc, posIdx, ne}); } } } if (answer >= INF/2) cout << -1 << "\n"; else cout << answer << "\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...