Submission #1135623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135623		Skymagic	Feast (NOI19_feast)	C++17	100 / 100	196 ms	12144 KiB

feast

/********************
 * what  the  sigma *
 ********************/
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(x) tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define ve vector
#define ll long long
#define ld long double
bool enabledb=0;
#define DB(CODE) cout<<'\t'<<CODE<<endl;
#define SP <<' '<<
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int, int>
#define tii tuple<int,int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define pb push_back
const ll mod = 1e9+7,maxn=200005;
const ll INF=(ll)1e18;
signed main() {
    int n,k;
    cin >> n >> k;
    ve<ll> a(n);
    for (int i=0;i<n;i++) {
        cin >> a[i];
    }
    auto solve=[&](ll lambda) {
        pll dp[n][2];
        dp[0][0]={0,0};
        dp[0][1]={a[0]-lambda,1};
        for (int i=1;i<n;i++) {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=max(make_pair(dp[i-1][1].f+a[i],dp[i-1][1].s),make_pair(dp[i-1][0].f+a[i]-lambda,dp[i-1][0].s+1));
        }
        return max(dp[n-1][0],dp[n-1][1]);
    };
    ll l=0,r=INF,m;
    while (l<r) {
        m=(l+r)>>1;
        if (solve(m).s>k) {
            l=m+1;
        } else {
            r=m;
        }
    }
    cout << solve(l).f+k*l;
}

• 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