Submission #1017334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017334		khanhtb	Feast (NOI19_feast)	C++14	100 / 100	113 ms	12180 KiB

feast

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vll vector<vi>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7;
const ll inf = 2e18;
const ll base = 31;
const ll blockdeg = 320;
const ll N = 3e5+8;
ll n,k,a[N];
pll dp[N][2];
pll solve_lambda(ll m){
    dp[1][0] = {0,0};
    dp[1][1] = {a[1]-m,1};
    for(ll i = 2; i <= n; i++){
        dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
        dp[i][1] = max(make_pair(dp[i-1][0].fi-m+a[i],dp[i-1][0].se+1),make_pair(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(ll i = 1; i <= n; i++) cin >> a[i];
    ll l = 0, r = 1e18;
    pll ans;
    ll lbd;
    while(l <= r){
        ll m = l+r>>1;
        pll s = solve_lambda(m);
        if(s.se <= k){
            ans = s;
            lbd = m;
            r = m-1;
        }
        else l = m+1;
    }
    cout << ans.fi+lbd*k;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen("test.inp","r")){
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ll T = 1;
    // cin >> T;
    for(ll i = 1; i <= T; i++){
        solve();
        // cout << '\n';
    }
}

Compilation message (stderr)

feast.cpp: In function 'void solve()':
feast.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         ll m = l+r>>1;
      |                ~^~
feast.cpp: In function 'int main()':
feast.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
feast.cpp: In function 'void solve()':
feast.cpp:48:23: warning: 'lbd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     cout << ans.fi+lbd*k;
      |                    ~~~^~

• 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