Submission #1209982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209982		44100	Feast (NOI19_feast)	C++20	100 / 100	109 ms	12176 KiB

feast

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pub push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll Max=3e5+5;
pll dp[Max][2];
ll a[Max],n,k;

pll process(ll la)
{
    ll i,j;
    dp[1][0]={0,0};
    dp[1][1]={a[1]-la,1};
    for(i=2;i<=n;++i)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=max(mp(dp[i-1][0].fi+a[i]-la,dp[i-1][0].se+1),mp(dp[i-1][1].fi+a[i],dp[i-1][1].se));
    }
    pll res=max(dp[n][0],dp[n][1]);
    return res;
}

ll solve() // Đổi tên từ solve2() thành solve()
{
    ll i,j,l,r;
    l=0;
    r=1e18;
    
    // Sử dụng binary search giống code AC
    while(l < r)
    {
        ll mid=(l+r+1)>>1; // Thêm +1 để tránh infinite loop
        pll res=process(mid);
        
        // Sửa logic: nếu số subarray >= k thì tăng l, ngược lại giảm r
        if(res.se >= k)
            l=mid;
        else 
            r=mid-1;
    }
    
    // Trả về kết quả cuối cùng
    pll final_res = process(l);
    return final_res.fi + l * k;
}

int main()
{
    fast
    ll i,j;
    cin>>n>>k;
    for(i=1;i<=n;++i)
        cin>>a[i];
    ll ans=solve(); // Giờ đã có hàm solve()
    cout<<ans<<"\n";
    return 0;
}

• 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