Submission #1278701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278701		jackofall718	Snail (NOI18_snail)	C++20	37 / 100	2 ms	580 KiB

snail

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

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

    ll H, N;
    cin >> H >> N;
    vector<ll> v(N);
    for (auto &x : v) cin >> x;

    // simulate first day
    ll height = 0;
    for (int i = 0; i < N; i++) {
        height = max(0LL, height + v[i]);
        if (height >= H) {
            cout << 0 << " " << i << "\n";
            return 0;
        }
    }

    ll daily_gain = accumulate(v.begin(), v.end(), 0LL);
    if (daily_gain <= 0) {
        cout << -1 << " " << -1 << "\n";
        return 0;
    }

    // number of full days needed before possibly escaping
    ll low = 0, high = (H / daily_gain) + 2, ans_day = -1, ans_phase = -1;
    while (low <= high) {
        ll mid = (low + high) / 2;
        ll hnow = mid * daily_gain;
        bool ok = false;
        ll tmp = hnow;
        for (int i = 0; i < N; i++) {
            tmp = max(0LL, tmp + v[i]);
            if (tmp >= H) {
                ans_day = mid;
                ans_phase = i;
                ok = true;
                break;
            }
        }
        if (ok) high = mid - 1;
        else low = mid + 1;
    }

    if (ans_day == -1) cout << -1 << " " << -1 << "\n";
    else cout << ans_day << " " << ans_phase << "\n";

    return 0;
}

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