Submission #1085240

#TimeUsernameProblemLanguageResultExecution timeMemory
1085240quan606303Feast (NOI19_feast)C++11
100 / 100
119 ms15240 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; pair<int,int> dp[maxn][2]; int a[maxn],n,k; pair<int,int> solve(int pen) { dp[1][0]={0,0}; dp[1][1]={a[1]-pen,1}; for (int i=2;i<=n;i++) { dp[i][0]=max(dp[i-1][0],dp[i-1][1]); dp[i][1]=max(make_pair(dp[i-1][0].fi+a[i]-pen,dp[i-1][0].se+1),make_pair(dp[i-1][1].fi+a[i],dp[i-1][1].se)); } return max(dp[n][0],dp[n][1]); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // file(""); cin>>n>>k; for (int i=1;i<=n;i++)cin>>a[i]; int l=0,r=1e18,ans=0; while (l<=r) { int mid=(l+r)/2; pair<int,int> cnt=solve(mid); if (cnt.se<=k) { ans=cnt.fi+cnt.se*mid; r=mid-1; } 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...