Submission #1228431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228431		surung9898	Snail (NOI18_snail)	C++20	100 / 100	1 ms	468 KiB

snail

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <random>
#ifdef _MSC_VER
#	include <intrin.h>
#	define __builtin_popcountll __popcnt
#endif

//#include <atcoder/all>
//using namespace atcoder;
//typedef modint998244353 mint;

using namespace std;

typedef long long int lld;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<lld, lld> pll;
typedef vector<int> vi;
typedef vector<lld> vl;
typedef vector<ld> vld;
typedef vector<char> vch;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vivi;
typedef vector<vl> vlvl;
typedef vector<vch> vcvc;
typedef vector<vb> vbvb;
typedef vector<vs> vsvs;

const lld mod = 1000000000000;
const lld inf = 1LL << 56;
const int nom = 200000;

int main()
{
    cin.tie(NULL), cout.tie(NULL);
    ios::sync_with_stdio(false);

    int n;
    lld h, mx = -inf, now = 0, diff = 0, fa = -1, fb = -1, tp;

    cin >> h >> n;

    vl vc(n);

    for (int i = 0; i < n; ++i)
        cin >> vc[i];

    for (int i = 0; i < n; ++i)
    {
        diff += vc[i];
        now = max(0LL, now + vc[i]);
        mx = max(mx, max(0LL, diff));
    }

    if (mx >= h)
    {
        fa = 0;
        diff = 0;

        for (int i = 0; i < n; ++i)
        {
            diff += vc[i];

            if (diff >= h)
            {
                fb = i;

                break;
            }
        }
    }
    else
    {
        fa = 1, tp = now;

        for (int i = 0; i < n; ++i)
        {
            now = max(0LL, now + vc[i]);

            if (now >= h)
            {
                fb = i;

                break;
            }
        }

        if (fb == -1)
        {
            h -= tp;

            if (diff <= 0)
                fa = fb = -1;
            else
            {
                h -= mx;
                fa = h / diff;
                h = h % diff + mx;

                diff = 0;

                while (diff < h)
                {
                    fa++;

                    for (int i = 0; i < n; ++i)
                    {
                        diff += vc[i];

                        if (diff >= h)
                        {
                            fb = i;

                            break;
                        }
                    }
                }
            }
        }
    }

    cout << fa << ' ' << fb;

    cout << '\n';

    return 0;
}

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