제출 #1129176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129176		jackofall718	Snail (NOI18_snail)	C++20	37 / 100	1 ms	584 KiB

snail

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H;
    int N;
    cin >> H >> N;  // well height, phases per day

    vector<ll> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
    }

    // 1) Build prefix array for one day with "clipping at 0"
    //    prefix[i] = height after i-th phase in the day
    //    (starting from height=0 at phase 0)
    //    If negative, clip to 0
    vector<ll> prefix(N);
    {
        ll curr = 0;
        for (int i = 0; i < N; i++) {
            curr += P[i];
            if (curr < 0) curr = 0;  // cannot go below 0
            prefix[i] = curr;
        }
    }

    // Check if snail exits on day 0 (the very first day):
    for (int i = 0; i < N; i++) {
        if (prefix[i] >= H) {
            cout << 0 << " " << i << "\n";
            return 0;
        }
    }

    // Net after one full day:
    ll net = prefix[N - 1];

    // If after one full day the snail is at 0 or has not progressed, it will never get out:
    if (net <= 0) {
        cout << -1 << " " << -1 << "\n";
        return 0;
    }

    // 2) If net > 0, we see how many full days we might skip.
    //    We want day D such that D * net is close to H but < H,
    //    then we simulate the partial day D.

    //    To be safe, we do day = (H-1) // net, because if day*net is already >= H,
    //    then the snail would have exited earlier.
    ll day = (H - 1) / net;  // 0-based day index
    ll heightSoFar = day * net; // snail's height at the start of "day" day.

    // Now simulate day "day" phase-by-phase:
    ll curr = heightSoFar;
    for (int i = 0; i < N; i++) {
        curr += P[i];
        if (curr < 0) curr = 0;
        if (curr >= H) {
            cout << day << " " << i << "\n";
            return 0;
        }
    }

    // If not out yet, it might mean we need day+1:
    // Because maybe heightSoFar + net < H, or the snail only gets out on the next day’s partial phases.
    day++;
    curr = day * net; // start of day (day+1 in 0-based)
    for (int i = 0; i < N; i++) {
        curr += P[i];
        if (curr < 0) curr = 0;
        if (curr >= H) {
            cout << day << " " << i << "\n";
            return 0;
        }
    }

    // If it still hasn't exited, theoretically we could keep going day+2, day+3, ...
    // But often the above logic is enough if the day stepping is chosen carefully.
    // For safety, you might loop a few more days, but typically the day calculation should suffice.

    // If for some reason we never exit:
    cout << -1 << " " << -1 << "\n";
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 9 / 9
• Subtask 3: 0 / 25
• Subtask 4: 17 / 17
• Subtask 5: 0 / 38