Submission #1018011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018011		vjudge1	Feast (NOI19_feast)	C++17	4 / 100	69 ms	15144 KiB

feast

#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define pb push_back
#define mod 1000000007
#define INF 2000000000
#define INF2 2000000000
#define fi first
#define se second
using namespace std;
double const EPS = 1e-10;
const int P = 1007;
typedef long long ll;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
const int N = 3e5 + 5;
ll arr[N];
pair<ll,int> dp[N][2];
int n, k;
pair<ll,int> sol(ll mid) {
    for(int i = 0; i <= n; i++) {
        dp[i][0].fi = 0;
        dp[i][1].fi = 0; 
        dp[i][0].se = 0;
        dp[i][1].se = 0;
    }
   // vector<int> pos;
    dp[0][1].fi -= mid;
    dp[0][1].se += 1;

    for(int i = 1; i <= n; i++) {

        if(dp[i-1][0].fi > dp[i-1][1].fi) dp[i][0].se = dp[i-1][0].se;
        else if(dp[i-1][0].fi < dp[i-1][1].fi) dp[i][0].se = dp[i-1][1].se;
        else dp[i][0].se = max(dp[i-1][0].se,dp[i-1][1].se);
        dp[i][0].fi = max(dp[i-1][0].fi,dp[i-1][1].fi);

        
        if(dp[i-1][1].fi+arr[i] < dp[i-1][0].fi+arr[i]-mid) {
            dp[i][1].se = dp[i-1][0].se+1; 
        }
        else if(dp[i-1][1].fi+arr[i] > dp[i-1][0].fi+arr[i]-mid) {
            dp[i][1].se = dp[i-1][1].se;
        }
        else {
            dp[i][1].se = max(dp[i-1][1].se,dp[i-1][0].se+1);
        }
        dp[i][1].fi = max(dp[i-1][1].fi+arr[i],dp[i-1][0].fi+arr[i]-mid);
    }
    if(dp[n][0].fi > dp[n][1].fi) return {dp[n][0].fi,dp[n][0].se};
    else if(dp[n][0].fi < dp[n][1].fi) return {dp[n][1].fi,dp[n][1].se};
    else return {dp[n][1].fi,max(dp[n][0].se,dp[n][1].se)};
}
int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    ll l = 0, r = INF;
    ll mx = 0;
    while(l <= r)  {
        ll mid = (l+r)/2;
        pair<ll,int> cal = sol(mid);
        if(cal.se <= k) {
           /* if(cal.se == k) {
                for(int i = 0; i <= n; i++) {
                    cout << i << ' ' << 'i' << endl;
                    cout << dp[i][0].fi << ' ' << dp[i][0].se << 'a' << endl;
                    cout << dp[i][1].fi << ' ' << dp[i][1].se << 'b' << endl;
                }
            }*/
            mx = max(cal.fi,mx);
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }
    cout << mx << endl;
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29