Submission #1330121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1330121		edo	Snail (NOI18_snail)	C++20	100 / 100	1 ms	348 KiB

snail

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    ll H;
    cin >> H >> n;
    vector<ll> h(n);
    for(auto &i : h) cin >> i;

    ll curr = 0;
    for(int i = 0; i < n; i++) { 
        curr = max(0ll, curr + h[i]);
        if(curr >= H) {
            cout << "0 " << i;
            exit(0);
        }
    }

    ll h0 = curr, h1 = h0;
    for(int i = 0; i < n; i++) {
        curr = max(curr + h[i], 0ll);
        h1 = max(h1, curr);
        if(curr >= H) {
            cout << "1 " << i;
            exit(0);
        }
    }
    
    ll h2 = curr;
    ll st = h2 - h0;
    if(st <= 0) {
        cout << "-1 -1";
        exit(0);
    }

    ll d = (H - h1 + st - 1) / st;
    ll left = H - d * st - h0;

    for(int i = 0; i < n; i++) {
        left -= h[i];
        if(left <= 0) {
            cout << d + 1 << " " << i;
            exit(0);
        }
    }

    return 0;
}

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