Submission #1194172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194172		zyntherix	Snail (NOI18_snail)	C++20	100 / 100	1 ms	328 KiB

snail

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define vi vector<int>
#define vs vector<string>
#define vb vector<bool>
#define vpi vector<pi>
#define pb push_back
#define all(a) (a).begin(), (a).end()
const int mod = 1e9 + 7;
int h, n;
vi v;
int s = 0, s2 = 0;
int kad = 0;

bool ok(int x)
{
    return (s + (s2 * (x - 1))) >= h - kad;
}

void solve()
{
    cin >> h >> n;
    v.resize(n);
    int c = 0;
    int ans = mod;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        s += v[i];
        s2 += v[i];
        c += v[i];
        kad = max(kad, c);
        if (s >= h)
        {
            ans = min(i, ans);
        }
        s = max(0ll, s);
    }
    if (ans != mod)
    {
        cout << "0 " << ans << '\n';
        return;
    }
    int l = 0;
    int r = 1;
    while (s > 0 && !ok(r))
        r *= 2;
    while (l + 1 < r)
    {
        int m = (l + r) / 2;
        if (ok(m))
        {
            r = m;
        }
        else
        {
            l = m;
        }
    }
    int curr = s + ((r - 1 > 0 ? r - 1 : 0) * (s2 > 0 ? s2 : 0));
    bool found = true;
    for (int i = 0; i < n; i++)
    {
        curr += v[i];
        curr = max(curr, 0ll);
        if (curr >= h)
        {
            cout << r << ' ' << i << '\n';
            return;
        }
    }
    cout << "-1 -1\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

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