#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 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... |