#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |