Submission #1147593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147593		jeremias	Feast (NOI19_feast)	C++20	0 / 100	33 ms	2492 KiB

feast

#include <bits/stdc++.h>
#define forn(i, n) for (tint i = 0; i < tint(n); i++)
#define forsn(i, s, n) for (tint i = s; i < tint(n); i++)
#define dforn(i, n) for (tint i = tint(n) - 1; i >= 0; i--)
#define dforsn(i, s, n) for (tint i = tint(n) - 1; i >= s; i--)
#define sz(x) tint(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;

using tint = long long;
using vi = vector<tint>;
using pii = pair<tint, tint>;

inline void fastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

inline string YN(bool x, string y = "YES", string n = "NO") { return (x ? y : n); }

template <typename T>
inline void chmax(T &lhs, T rhs)
{
    lhs = max(lhs, rhs);
}

template <typename T>
inline void chmin(T &lhs, T rhs)
{
    lhs = min(lhs, rhs);
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "[";
    forn(i, sz(v))
    {
        if (i > 0)
            os << ", ";
        os << v[i];
    }
    os << "]";
    return os;
}

template <typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &v)
{
    os << "[";
    forn(i, N)
    {
        if (i > 0)
            os << ", ";
        os << v[i];
    }
    os << "]";
    return os;
}

int main()
{
    fastIO();
    tint n, k;
    cin >> n >> k;
    vi arr;
    tint curr = 0, prevSign = -1, start = 0, pos = 0;
    forn(i, n)
    {
        tint el;
        cin >> el;
        bool sign = (el >= 0);
        if (prevSign != -1 && prevSign != sign)
        {
            arr.push_back(curr);
            pos += (curr > 0);
            start += curr * (curr > 0);
            curr = 0;
        }
        curr += el;
        prevSign = sign;
    }
    pos += (curr > 0);
    start += curr * (curr > 0);
    arr.push_back(curr);
    arr.push_back(0);
    n = sz(arr);

    auto f = [&](tint lam)
    {
        tint ret = start - lam * pos, left = 0;
        forn(i, n - 1)
        {
            if (arr[i] <= 0)
                continue;
            ret += max(0LL, lam - min(arr[i], -arr[i + 1]));
        }
        return -(ret + lam * k);
    };

    tint l = 0, r = 1e9;
    while (r - l > 2)
    {
        tint m1 = l + (r - l) / 3;
        tint m2 = r - (r - l) / 3;
        tint f1 = f(m1);
        tint f2 = f(m2);
        if (f1 < f2)
            l = m1;
        else
            r = m2;
    }
    tint ans = -1e9;
    forsn(i, l, r + 1) chmax(ans, f(i));
    cout << -ans << "\n";
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29