Submission #1017285

#TimeUsernameProblemLanguageResultExecution timeMemory
1017285ThanhsFeast (NOI19_feast)C++14
100 / 100
120 ms15188 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long // #define double long double #define pb push_back #define endl '\n' #define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define setmin(x,y) x=min((x),(y)) #define setmax(x,y) x=max((x),(y)) #define fi first #define se second mt19937 hdp(69420); int rand(int l,int r){return l+((hdp()%(r-l+1))+r-l+1)%(r-l+1);} const int N = 3e5 + 5; const int mod = 1e9 + 7; const int SQ = 450; const int inf = 1e17; const int L = 40; int n,k,a[N]; pair<int,int> dp[N][2]; pair<int,int> solve(int lambda) { for(int i=1;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]-lambda,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]); } signed main() { fastIO // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); dp[0][1]={-inf,0}; cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; int l=0,r=inf; while(l<r-1) { int m=l+r>>1; auto res=solve(m); if(res.se>k) l=m; else r=m; } auto res=solve(r); cout<<res.fi+res.se*r; }

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:49:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int m=l+r>>1;
      |               ~^~
#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...