Submission #1085265

#TimeUsernameProblemLanguageResultExecution timeMemory
1085265quan606303Feast (NOI19_feast)C++14
100 / 100
108 ms12884 KiB
///0-0 : what is your motivation, quan606303? ///quan606303 : Hutao /*idea : */ #include <bits/stdc++.h> #define int long long #define ll long long #define INTMAX INT_MAX #define INTMIN INT_MIN #define LONGMAX LLONG_MAX #define LONGMIN LLONG_MIN #define fi first #define se second #define memfull(a,b) memset(a,b,sizeof(a)); #define endl '\n' #define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout); using namespace std; const int MOD=1e9+7; const int maxn=3e5+7;; int n,k,a[maxn],pre[maxn]; pair<int,int> dp[maxn]; pair<int,int> sub1(int pen) { pair<int,int> cnt={0,0}; for (int i=1;i<=n;i++) { dp[i]=max(dp[i-1],make_pair(cnt.fi+pre[i]-pen,cnt.se+1)); cnt=max(cnt,make_pair(dp[i].fi-pre[i],dp[i].se)); } return dp[n]; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // file("MUABANCO"); cin>>n>>k; for (int i=1;i<=n;i++)cin>>a[i]; for (int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i]; int l=0,r=1e18,ans=0; while (l<=r) { int mid=(l+r)/2; pair<int,int> cnt=sub1(mid); if (cnt.se<=k) { r=mid-1; ans=cnt.fi+cnt.se*mid; } else l=mid+1; } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...