Submission #1203191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203191		kim	Feast (NOI19_feast)	C++20	100 / 100	60 ms	7424 KiB

feast

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define add(x,y) ((((x)+(y))%md+md)%md)
#define Add(x,y) (x=add(x,y))
#define mul(x,y) ((((x)*(y))%md+md)%md)
#define Mul(x,y) (x=mul(x,y))
template<class T> T chmn(T &x,T y){ return x=min(x,y); }
template<class T> T chmx(T &x,T y){ return x=max(x,y); }
const int inf=1e9;
const ll linf=1e18;
const ll md=1e9+7;
// const ll md=119<<23|1;

ll a[300005];

pair<ll,ll> dp[300005];
void calc(int n,ll c){
  pair<ll,ll> mx(0,0);
  for(int i=1;i<=n;++i){
    dp[i] = max(dp[i-1], {mx.f+a[i]-c, mx.s-1});
    chmx(mx, {dp[i].f-a[i], dp[i].s});
  }
}

void solve(){
  int n,k; cin>>n>>k;
  for(int i=1;i<=n;++i) cin>>a[i], a[i]+=a[i-1];
  ll l=0,r=1e15;
  while(l<r){
    ll mid=l+r>>1;
    calc(n,mid);
    if(-dp[n].s<=k) r=mid;
    else l=mid+1;
  }
  calc(n,l);
  cout << dp[n].f+l*k;
}

int main(){
  ios::sync_with_stdio(false); cin.tie(0);

  int Q(1);
  // cin>>Q;
  while(Q--) solve();

}
/*

6 1
1 -2 3 -1 5 -6

6 2
1 2 3 -10 5 6

*/

• 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