oj.uz

Submission #1027485

# Submission time Handle Problem Language Result Execution time Memory
1027485 2024-07-19T06:57:40 Z caterpillow Feast (NOI19_feast) C++17
12 / 100
 67 ms 12892 KB 
#include <bits/stdc++.h>

using namespace std;

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<typename Tuple, size_t... Is>
void print_tuple(const Tuple& t, index_sequence<Is...>) {
    ((cerr << (Is == 0 ? "{" : ", ") << get<Is>(t)), ...);
    cerr << "}";
}

template<typename... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
    print_tuple(t, index_sequence_for<Args...>{});
    return os;
}

ostream& operator<<(ostream& os, string& s) {
    for (char c : s) os << c; 
    return os;
}

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

template<typename T, typename V>
ostream& operator<<(ostream& os, const pair<T, V> p) {
    os << "{" << p.f << ", " << p.s << "}";
    return os;
}

template <typename T, typename... V>
void printer(const char *names, T &&head, V &&...tail) {
    int i = 0;
    while (names[i] != '\0' && names[i] != ',') i++;
    constexpr bool is_str = is_same_v<decay_t<T>, const char*>;
    if constexpr (is_str) cerr << head; // ignore directly passed strings
    else cerr.write(names, i) << " = " << head; 
    if constexpr (sizeof...(tail)) cerr << (is_str ? "" : ","), printer(names + i + 1, tail...);
    else cerr << endl;
}

#ifdef LOCAL
#define dbg(...) std::cerr << __LINE__ << ": ", printer(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

aliens trick

dp[i] = max value of eating first i dishes
dp[i] = min(dp[i - 1], max (j < i) dp[j] + sfx[j] - sfx[i + 1])

*/

ll n, k;
vt<ll> a, sfx;

// tiebreak by minimum # of arrays used
pl check(ll penalty) {
    vt<pl> dp(n + 1);
    ll best = sfx[0], used = 0;
    F0R (i, n) {
        dp[i + 1] = dp[i];
        if (best - sfx[i + 1] - penalty > dp[i + 1].f) {
            dp[i + 1] = {best - sfx[i + 1] - penalty, used + 1};
        } else if (best - sfx[i + 1] - penalty == dp[i + 1].f && used + 1 < dp[i + 1].s) {
            dp[i + 1] = {best - sfx[i + 1] - penalty, used + 1};
        }
        if (dp[i + 1].f + sfx[i + 1] > best) tie(best, used) = dp[i + 1], best += sfx[i];
        else if (dp[i + 1].f + sfx[i + 1] == best && used > dp[i + 1].s) tie(best, used) = dp[i + 1], best += sfx[i];
    }
    return dp[n];
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> k;
    a.resize(n);
    sfx.resize(n + 1);
    F0R (i, n) cin >> a[i];
    copy(all(a), sfx.begin());
    ROF (i, 0, n) sfx[i] += sfx[i + 1];

    // more penalty = fewer arrays
    // want to find smallest penalty such that <= k arrays
    ll lo = -1, hi = 1e12;
    while (hi - lo > 1) {
        ll m = (lo + hi) / 2;
        auto [cost, used] = check(m);
        if (used > k) lo = m;
        else hi = m;
    }
    auto [cost, used] = check(hi);
    ll ans = cost + hi * k;
    cout << ans << endl;
}

Compilation message

feast.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main() {
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 12180 KB Output is correct
2 Correct 42 ms 12580 KB Output is correct
3 Correct 56 ms 12892 KB Output is correct
4 Correct 40 ms 12628 KB Output is correct
5 Correct 43 ms 12548 KB Output is correct
6 Correct 56 ms 12380 KB Output is correct
7 Correct 39 ms 12180 KB Output is correct
8 Correct 45 ms 12380 KB Output is correct
9 Correct 45 ms 12628 KB Output is correct
10 Correct 40 ms 12368 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 10620 KB Output is correct
2 Correct 35 ms 10836 KB Output is correct
3 Correct 35 ms 10624 KB Output is correct
4 Correct 35 ms 10588 KB Output is correct
5 Correct 49 ms 12184 KB Output is correct
6 Correct 35 ms 10568 KB Output is correct
7 Correct 44 ms 10912 KB Output is correct
8 Correct 43 ms 12612 KB Output is correct
9 Correct 42 ms 12320 KB Output is correct
10 Correct 34 ms 10840 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 12760 KB Output is correct
2 Correct 56 ms 12404 KB Output is correct
3 Incorrect 60 ms 12624 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 12180 KB Output is correct
2 Correct 42 ms 12580 KB Output is correct
3 Correct 56 ms 12892 KB Output is correct
4 Correct 40 ms 12628 KB Output is correct
5 Correct 43 ms 12548 KB Output is correct
6 Correct 56 ms 12380 KB Output is correct
7 Correct 39 ms 12180 KB Output is correct
8 Correct 45 ms 12380 KB Output is correct
9 Correct 45 ms 12628 KB Output is correct
10 Correct 40 ms 12368 KB Output is correct
11 Correct 35 ms 10620 KB Output is correct
12 Correct 35 ms 10836 KB Output is correct
13 Correct 35 ms 10624 KB Output is correct
14 Correct 35 ms 10588 KB Output is correct
15 Correct 49 ms 12184 KB Output is correct
16 Correct 35 ms 10568 KB Output is correct
17 Correct 44 ms 10912 KB Output is correct
18 Correct 43 ms 12612 KB Output is correct
19 Correct 42 ms 12320 KB Output is correct
20 Correct 34 ms 10840 KB Output is correct
21 Correct 67 ms 12760 KB Output is correct
22 Correct 56 ms 12404 KB Output is correct
23 Incorrect 60 ms 12624 KB Output isn't correct
24 Halted 0 ms 0 KB -