Submission #1112898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112898		KhoaHo	Feast (NOI19_feast)	C++17	100 / 100	137 ms	15180 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define task "test"
#define pb push_back
#define SZ(a) (a).begin(), (a).end()
#define SZZ(a, Begin, End) (a) + (Begin), (a) + (Begin) + (End)
#define BIT(a) (1LL << (a))
#define vec vector
#define fi first
#define se second
#define mp make_pair
#define MASK(x, i) (((x) >> (i))&1)
typedef long long ll;
typedef pair<ll, ll> ii;
template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }
void fastio() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    if (fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    else if (fopen(task ".in", "r")) {
        freopen(task ".in", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
}
const int N = int(3e5) + 100;
const ll INF = 1e18;
int n, k;
ll a[N];
ii dp[N][2];
void init() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
}
// dp(i, 0) = dp(i - 1, 0) + a  
ii calc(ll C) {
    dp[1][0] = ii(0, 0);
    dp[1][1] = ii(a[1] - C, 1);
    for(int i = 2; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);

        dp[i][1] = max(ii(dp[i - 1][0].fi + a[i] - C, dp[i - 1][0].se + 1),
                       ii(dp[i - 1][1].fi + a[i], dp[i - 1][1].se));
    }
    return max(dp[n][0], dp[n][1]);
}
void process(const int &tc) {
    ll l = 0, r = 1e18;
    ll ans = 0;
    while(l <= r) {
        ll mid = l + (r - l)/2;
        if(calc(mid).se <= k) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    ii res = calc(ans);
    cout << res.fi + res.se * ans;
}
int main() {
    fastio();
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        init();
        process(i);
    }
    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'void fastio()':
feast.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(task ".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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