제출 #1313315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313315		jahongir	Feast (NOI19_feast)	C++20	100 / 100	68 ms	10952 KiB

feast

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef vector<int> vi;



const int mxn = 3e5;
int arr[mxn];
pair<ll,int> dp[mxn][2];
int n,k;


pair<ll,int> get(ll lambda){
    dp[0][0] = {0,0};
    dp[0][1] = {arr[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(pair<ll,int>{dp[i-1][0].first+arr[i]-lambda,dp[i-1][0].second+1},
                       pair<ll,int>{dp[i-1][1].first+arr[i],dp[i-1][1].second});
    }
    return max(dp[n-1][0],dp[n-1][1]);
}



void solve(){
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> arr[i];

    ll l = 0, r = 1e15;

    while(l+1 < r){
        ll mid = (l+r)>>1;
        auto [ans,res] = get(mid);
        if(res >= k) l = mid;
        else r = mid;
    }

    cout << get(l).first + k*l;
}   


signed main(){
    cin.tie(0)->sync_with_stdio(0);


    int t = 1;
    // cin >> t;
    while(t--){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