Submission #791938

#TimeUsernameProblemLanguageResultExecution timeMemory
791938trucmaiFeast (NOI19_feast)C++17
100 / 100
105 ms8012 KiB
//i_love_aisukiuwu #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "/home/trucmai/.vim/tools.h" #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl; #else #define debug(x...) #endif void open(){ if(fopen("i.inp","r")){ freopen("i.inp","r",stdin); freopen("o.out","w",stdout); } } #define ll long long #define all(a) (a).begin(), (a).end() #define vi vector<ll> #define pi pair<ll,ll> #define pii pair<ll,pair<ll,ll>> #define fi first #define se second #define gcd __gcd #define mset(a,v) memset(a, v, sizeof(a)) #define endl '\n' #define spc " " const int MN1 = 1e6 + 5,MN2 = 2e3 + 5,LOG = 27; const ll MOD = 1e9 + 7,INF = 1e9; ll n,k,a[MN1],pf[MN1]; void solve(){ cin>>n>>k; for(ll i = 1;i <= n;++i){ cin>>a[i]; pf[i] = pf[i-1] + a[i]; } ll l = 0,r = 3e14,res = 0; auto dp=[&](ll x)->pi{ pi mx = {0,0},f = {0,0}; for(ll i = 1;i <= n;++i){ f = max(f,{mx.fi + pf[i] - x,mx.se - 1}); mx = max(mx,{f.fi - pf[i],f.se}); } f.se *= -1; return f; }; while(l <= r){ ll m = (r+l) >> 1; auto [val,cnt] = dp(m); debug(l,r,cnt); if(cnt <= k){ r = m - 1; res = val + k*m; } else l = m + 1; } cout<<res; } signed main(){ cin.tie(0) -> sync_with_stdio(0); open(); ll t = 1; //cin>>t; while(t--) solve(); #ifdef LOCAL cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif }

Compilation message (stderr)

feast.cpp: In function 'void open()':
feast.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("i.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
feast.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("o.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
#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...