Submission #503429

#	Time	Username	Problem	Language	Result	Execution time	Memory
503429		maximumSHOT	Feast (NOI19_feast)	C++17	100 / 100	392 ms	16456 KiB

feast

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

const int inf = 1e9;
const ll inf64 = 1e18;

struct output {
    ll res;

    void print() {
        cout << res << "\n";
    }

    bool operator == (const output& o) const {
        return res == o.res;
    }
};

struct input {
    int n, k;
    vector<int> a;
    vector<ll> pref;

    input() = default;

    void read() {
        cin >> n >> k;
        a.resize(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> a[i];
    }

    void print() {
        cout << n << " " << k << "\n";
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << "\n";
    }

    void gen() {
        static mt19937 rnd(42);
        const int MAXN = 10;
        const int MAXX = 10;
        n = rnd() % MAXN + 1;
        k = rnd() % n + 1;
        a.resize(n + 1);
        for (int i = 1; i <= n; i++)
            a[i] = rnd() % (2 * MAXX + 1) - MAXX;
    }

    void gen_max_test() {

    }

    pair<ll, int> check(ll lambda) {
        vector<pair<ll, int>> dp(n + 1, make_pair(-inf64, -inf)), pr = dp;
        pr[0] = {0, 0};
        pair<ll, int> mx = {pr[0].first - pref[0], pr[0].second};
        for (int i = 1; i <= n; i++) {
            {
                pair<ll, int> tmp = {
                    mx.first + (pref[i]) - lambda,
                    mx.second + 1
                };
                dp[i] = max(dp[i], tmp);
            }
            pr[i] = max(pr[i - 1], dp[i]);
            mx = max(mx, make_pair(pr[i].first - pref[i], pr[i].second));
        }
        pair<ll, int> res = {-inf64, -inf};
        for (int i = 1; i <= n; i++)
            res = max(res, dp[i]);
        return res;
    }

    output fast() {
        pref.assign(n + 1, 0);
        for (int i = 1; i <= n; i++)
            pref[i] = pref[i - 1] + a[i];
        ll bl = 0, br = inf64 / 3, bm;
        while (br - bl > 1) {
            bm = bl + (br - bl) / 2;
            auto tmp = check(bm);
            if (tmp.second >= k) bl = bm;
            else br = bm;
        }
        ll res = 0;
        auto tmp = check(bl);
        res = max(res, tmp.first + 1ll * bl * k);
        return output{res};
    }

    output slow() {
#ifndef DEBUG
        throw;
#endif

        vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, -inf64));
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int c = 0; c <= k; c++) {
                dp[i][c] = max(dp[i - 1][c], c ? dp[i][c - 1] : -inf64);
                ll sm = 0;
                for (int j = i; j >= 1; j--) {
                    sm += a[j];
                    dp[i][c] = max(dp[i][c], (c ? dp[j - 1][c - 1] : -inf64) + sm);
                }
            }
        }

        return output{dp[n][k]};
    }
};

void test_case() {
    input in;
    in.read();
    output res = in.fast();
    res.print();
}

void work() {
    int t = 1;
    while (t--)
        test_case();
}

void test() {
    for (int t = 1;;t++) {
        input in;
        in.gen();
        input in_fs = in;
        input in_sl = in;
        output fs = in_fs.fast();
        output sl = in_sl.slow();
        if (fs == sl) {
            cout << "OK" << endl;
            fs.print();
            cout << "\n=========" << endl;
        } else {
            cout << "WA " << t << "\n";
            cout << "exp\n";
            sl.print();
            cout << "\n=========\n";
            cout << "fnd\n";
            fs.print();
            cout << "\n=========\n";
            in.print();
            break;
        }
    }
}

void max_test() {
    input in;
    in.gen_max_test();
    input in_fs = in;
    output fs = in_fs.fast();
    fs.print();
}

int main() {

#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    work();
//    test();
//    max_test();

    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'void max_test()':
feast.cpp:27:8: warning: 'in.input::n' is used uninitialized in this function [-Wuninitialized]
   27 | struct input {
      |        ^~~~~
feast.cpp:27:8: warning: 'in' is used uninitialized in this function [-Wuninitialized]

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