제출 #1224923

#제출 시각아이디문제언어결과실행 시간메모리
1224923AlgorithmWarriorFeast (NOI19_feast)C++20
100 / 100
177 ms8632 KiB
#include <bits/stdc++.h> using namespace std; struct answer{ long long sum; int cnt; bool operator<(answer ot){ if(sum!=ot.sum) return sum<ot.sum; return cnt>ot.cnt; } }; int const NMAX=300005; answer dp[NMAX]; int n,k; int v[NMAX]; long long sp[NMAX]; void read(){ cin>>n>>k; int i; for(i=1;i<=n;++i){ cin>>v[i]; sp[i]=sp[i-1]+v[i]; } } answer get_dp(long long lambda){ answer best={0,0}; int i; for(i=1;i<=n;++i){ dp[i]={best.sum+sp[i]-lambda,best.cnt+1}; if(dp[i]<dp[i-1]) dp[i]=dp[i-1]; answer best2={dp[i].sum-sp[i],dp[i].cnt}; if(best<best2) best=best2; } return dp[n]; } long long bin_search(){ /// (] long long st=-1,dr=300000000000000; while(dr-st>1){ long long mij=(st+dr)/2; if(get_dp(mij).cnt<k) dr=mij; else st=mij; } return get_dp(dr).sum+dr*k; } int main() { read(); cout<<bin_search(); 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...