Submission #991316

#	Time	Username	Problem	Language	Result	Execution time	Memory
991316		vjudge1	Feast (NOI19_feast)	C++17	100 / 100	103 ms	12172 KiB

feast

#include<bits/stdc++.h>
#include<ext/numeric>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define Fast ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
#define int long long
template<class T> using ordered_set = tree<T, null_type , less<T> ,rb_tree_tag , tree_order_statistics_node_update> ;
typedef long long ll;
const int N=3e5+3,LG=__lg(N)+2,M=21,MOD=998244353,inf=3e14;
pair<int,int> dp[2][N];
int v[N],n;
pair<int,int> sol(int mid) {
    dp[0][0] = {0, 0};
    dp[1][0] = {v[0] - mid, 1};

    for (int i = 1; i < n; i++) {
        dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);

        dp[1][i] =
                max(make_pair(dp[0][i - 1].first + v[i] - mid,
                              dp[0][i - 1].second + 1),
                    make_pair(dp[1][i - 1].first + v[i], dp[1][i - 1].second));
    }

    return max(dp[0][n - 1], dp[1][n - 1]);
}
void solve() {
    int k;
    cin>>n>>k;
    for (int i = 0; i <n ; ++i)
        cin>>v[i];
    int l=0,r=inf;
    while(r-l>1){
        int mid=l+(r-l)/2;
        if(sol(mid).second<k)
            r=mid;
        else l=mid;
    }
    cout<<sol(l).first+l*k<<'\n';
}
signed main() {
    Fast;
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; ++i) {
        // cout<<"Case #"<<i<<": ";
        solve();
    }
}

• 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