Submission #1063886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063886		seoul_korea	Feast (NOI19_feast)	C++17	100 / 100	832 ms	27048 KiB

feast

// Goten2308
#include<bits/stdc++.h>

using namespace std;
#define int long long
using ll = long long;
using ii = pair <int, int>;
#define fi first
#define se second 
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define BIT(x, y) ((x >> y) & 1)
#define MASK(x) (1 << x)
#define MOD 1000000007
#define MULTI_TEST1
#define __GOTEN_WILL_BE_BETTER__ signed main()
template <class T> bool maximize(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template <class T> bool minimize(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template <class T> void add(T& a, T b) { a += b; if(a >= MOD) a -= MOD; }
template <class T> void sub(T& a, T b) { a -= b; if(a < 0) a += MOD; }

const int maxN = 300100, INF = (int)1e18 + 7;
int n, k;
int a[maxN];

pair<int, int> solveLambda(int x) {
    vector< vector<ii> > dp(n + 1, vector<ii>(2, mp(-INF, -INF)));
    // dp[0][0] = mp(-x, 1);
    // dp[0][1] = mp(-x, 1);
    for(int i = 1; i <= n; i++) {
        dp[i][1] = mp(a[i] - x, 1);
    }
    for(int i = 1; i <= n; i++) {
        maximize(dp[i][0], max(mp(dp[i - 1][0].fi, dp[i - 1][0].se), mp(dp[i - 1][1].fi, dp[i - 1][1].se)));
        maximize(dp[i][1], max(mp(dp[i - 1][0].fi + a[i] - x, dp[i - 1][0].se + 1), mp(dp[i - 1][1].fi + a[i], dp[i - 1][1].se)));
    }
    return max(dp[n][0], dp[n][1]);
}

void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int l = 0, r = (int)1e13 + 7;
    while(r - l > 1) {
        int m = l + r >> 1;
        if(solveLambda(m).se >= k) l = m;
        else r = m;
    }
    cout << solveLambda(l).fi + k * l << endl;
}

__GOTEN_WILL_BE_BETTER__ {
    #define task ""
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }
    cin.tie(0)->ios_base::sync_with_stdio(0);
    int nTest = 1;
    #ifdef MULTI_TEST
    cin >> nTest;
    #endif
    while(nTest--) {
        solve();
    }
    cout << endl;
    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'void solve()':
feast.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int m = l + r >> 1;
      |                 ~~^~~
feast.cpp: In function 'int main()':
feast.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         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