Submission #1104198

#TimeUsernameProblemLanguageResultExecution timeMemory
1104198nasir_bashirovFeast (NOI19_feast)C++17
0 / 100
129 ms13896 KiB
// #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> #define vl vector<ll> #define vii vector<pii> #define db long double #define vll vector<pll> #define endl '\n' #define all(x) x.begin(), x.end() #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define int long long const int sz = 3e5 + 5; int n, k, a[sz]; pii dp[sz][2]; void calc(int mid){ dp[1][0] = {0, 0}, dp[1][1] = {a[1] - mid, 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].first + a[i] - mid, dp[i - 1][0].second + 1), make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second)); } } void fmain(){ cin >> n >> k; int cnt = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; if(a[i] > 0) cnt++; } k = min(k, cnt); int l = 0, r = 1e14, res = 0; while(l <= r){ int mid = (l + r) / 2; calc(mid); if(max(dp[n][0], dp[n][1]).second >= k){ res = max(res, max((dp[n][1].first + k * mid) * (dp[n][1].second >= k), (dp[n][0].first + k * mid) * (dp[n][1].second >= k))); // cout << mid << " " << dp[n][0].first << " " << dp[n][0].second << " " << dp[n][1].first << " " << dp[n][1].second << endl; // cout << (dp[n][1].first + k * mid) * (dp[n][1].second >= k) << " " << (dp[n][0].first + k * mid) * (dp[n][1].second >= k) << endl << endl; l = mid + 1; } else{ r = mid - 1; } } cout << res; } signed main(){ int tmr = 1; //cin >> tmr; while(tmr--){ fmain(); } }
#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...