Submission #1265653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265653		witek_cpp	Dungeon 3 (JOI21_ho_t5)	C++20	0 / 100	4091 ms	2162688 KiB

Main

#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), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) cin >> B[i];

    // pref dla wygody (pref[0]=0, pref[i]=sum A[0..i-1])
    vector<ll> pref(N+1, 0);
    for (int i = 1; i <= N; ++i) pref[i] = pref[i-1] + A[i-1];

    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; }

        // check impossible if some A[i] > U on route
        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; }

        ll Ucap = min<ll>(U, totalNeeded);
        int L = T - S; // positions: p = 0..L (S..T), segments are 0..L-1
        int Mdim = L + 1; // we'll use indexing id = p*Mdim + x, x in [0..L]

        // precompute maxX[p] = largest x such that sum A[S+p .. S+x-1] <= Ucap
        vector<int> maxX(Mdim, -1);
        for (int p = 0; p <= L; ++p) {
            int lo = p, hi = L;
            int best = p;
            while (lo <= hi) {
                int mid = (lo + hi) >> 1;
                ll sum = pref[S + mid] - pref[S + p];
                if (sum <= Ucap) { best = mid; lo = mid + 1; }
                else hi = mid - 1;
            }
            maxX[p] = best; // there is always at least x = p (sum = 0)
        }

        // Number of potential nodes = Mdim * Mdim (we'll ignore invalid by checks)
        int totalStates = Mdim * Mdim;
        vector<ll> dist(totalStates, INF);
        auto idx = [&](int p, int x){ return p * Mdim + x; };

        // Dijkstra
        using pli = pair<ll,int>;
        priority_queue<pli, vector<pli>, greater<pli>> pq;

        // start (p=0,x=0)
        dist[idx(0,0)] = 0;
        pq.push({0, idx(0,0)});

        ll answer = INF;
        int targetId = idx(L, L);

        while (!pq.empty()) {
            auto [curCost, id] = pq.top(); pq.pop();
            if (curCost != dist[id]) continue;
            if (id == targetId) { answer = curCost; break; }
            int p = id / Mdim;
            int x = id % Mdim;
            // skip invalid node (x must be between p and maxX[p])
            if (x < p || x > maxX[p]) continue;

            // 1) move to next floor without buying if possible: (p,x) -> (p+1,x) cost 0
            if (p < L && x > p) { // x>p means energy >= A[S+p]
                int nid = idx(p+1, x);
                if (dist[nid] > curCost) {
                    dist[nid] = curCost;
                    pq.push({curCost, nid});
                }
            }

            // 2) buy "one segment" more: (p,x) -> (p,x+1) cost A[S+x] * B[S+p]
            if (x < Mdim - 1 && x+1 <= maxX[p]) {
                ll add = (ll)A[S + x] * (ll)B[S + p];
                int nid = idx(p, x+1);
                if (dist[nid] > curCost + add) {
                    dist[nid] = curCost + add;
                    pq.push({dist[nid], nid});
                }
            }
        }

        if (answer >= INF/4) cout << -1 << '\n';
        else cout << answer << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 31
• Subtask 4: 0 / 44