oj.uz

Submission #503421

# Submission time Handle Problem Language Result Execution time Memory
503421 2022-01-07T22:38:13 Z maximumSHOT Feast (NOI19_feast) C++17
4 / 100
 33 ms 4296 KB 
#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() {

    }

    void gen() {
        // use static
    }

    void gen_max_test() {

    }

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

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

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

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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1356 KB Output is correct
2 Correct 31 ms 4280 KB Output is correct
3 Correct 30 ms 4296 KB Output is correct
4 Correct 28 ms 4288 KB Output is correct
5 Correct 31 ms 4280 KB Output is correct
6 Correct 27 ms 4140 KB Output is correct
7 Correct 33 ms 4120 KB Output is correct
8 Correct 32 ms 4280 KB Output is correct
9 Correct 27 ms 4256 KB Output is correct
10 Correct 28 ms 4272 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1356 KB Output is correct
2 Correct 19 ms 2612 KB Output is correct
3 Incorrect 19 ms 2480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 1356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1356 KB Output is correct
2 Correct 31 ms 4280 KB Output is correct
3 Correct 30 ms 4296 KB Output is correct
4 Correct 28 ms 4288 KB Output is correct
5 Correct 31 ms 4280 KB Output is correct
6 Correct 27 ms 4140 KB Output is correct
7 Correct 33 ms 4120 KB Output is correct
8 Correct 32 ms 4280 KB Output is correct
9 Correct 27 ms 4256 KB Output is correct
10 Correct 28 ms 4272 KB Output is correct
11 Correct 17 ms 1356 KB Output is correct
12 Correct 19 ms 2612 KB Output is correct
13 Incorrect 19 ms 2480 KB Output isn't correct
14 Halted 0 ms 0 KB -