Submission #930172

#TimeUsernameProblemLanguageResultExecution timeMemory
930172ASN49KFeast (NOI19_feast)C++14
100 / 100
89 ms5736 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define int long long const int inf=1e12; using i64=long long; int n; vector<int>a; pair<int64_t, int64_t> dp(int64_t lambda) { int64_t mu = 0, nu = 0, p = 0, cnt = 0, _cnt = 0; for (size_t i = 0; i < n; ++i) { p += a[i]; if (mu + p - lambda > nu) nu = mu + p - lambda, _cnt = cnt + 1; if (nu - p > mu) cnt = _cnt, mu = nu - p; } return {nu, _cnt}; } main() { ios::sync_with_stdio(false); cin.tie(0); int k; cin>>n>>k; a.resize(n); for(int i=0;i<n;i++) { cin>>a[i]; } int st=0,dr=inf; i64 rez=-1e18; while(st<=dr) { int m=(st+dr)/2; auto xd=dp(m); if(xd.second <= k) { dr=m-1; rez=xd.first+1LL*k*m; } else { st=m+1; } } cout<<rez; return 0; } /*#include <bits/stdc++.h> using namespace std; constexpr size_t N = 300000; int64_t a[N]; pair<int64_t, int64_t> dp(size_t n, int64_t lambda) { int64_t mu = 0, nu = 0, p = 0, cnt = 0, _cnt = 0; for (size_t i = 0; i < n; ++i) { p += a[i]; if (mu + p - lambda > nu) nu = mu + p - lambda, _cnt = cnt + 1; if (nu - p > mu) cnt = _cnt, mu = nu - p; } return {nu, _cnt}; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); size_t n, k; cin >> n >> k; for (size_t i = 0; i < n; ++i) cin >> a[i]; int64_t u = 0, v = 1LL << 55; while (u < v) { if (dp(n, (u + v) / 2).second <= k) v = (u + v) / 2; else u = (u + v) / 2 + 1; } //auto const [objective_val, cnt] = dp(n, u); cout << dp(n,u).first + k * u << '\n'; }*/

Compilation message (stderr)

feast.cpp: In function 'std::pair<long int, long int> dp(int64_t)':
feast.cpp:14:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   14 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~
feast.cpp: At global scope:
feast.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main()
      | ^~~~
#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...