Submission #448250

#TimeUsernameProblemLanguageResultExecution timeMemory
448250JovanB도넛 (JOI14_ho_t3)C++17
100 / 100
79 ms4468 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; ll pre[200005]; int lp, rp; ll ternary(int l, int r){ if(r-l <= 3){ ll mn = 1e18; for(int i=l; i<=r; i++){ ll x = abs(pre[i]-pre[lp-1]-(pre[rp]-pre[i])); mn = min(mn, x); } return (pre[rp]-pre[lp-1]-mn)/2; } int a = l + (r-l)/3; int b = r - (r-l)/3; ll a1 = abs(pre[a]-pre[lp-1]-(pre[rp]-pre[a])); ll b1 = abs(pre[b]-pre[lp-1]-(pre[rp]-pre[b])); if(a1 == b1) return ternary(a, b); if(a1 < b1) return ternary(l, b); if(a1 > b1) return ternary(a, r); } ll a[200005]; int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; int n; cin >> n; for(int i=1; i<=n; i++){ cin >> a[i]; a[i+n] = a[i]; } for(int i=1; i<=2*n; i++){ pre[i] = pre[i-1]+a[i]; } int r = 1; ll res = 0; for(int l=1; l<=n; l++){ lp = r+1; rp = l+n-1; while(ternary(r+1, l+n-1) >= pre[r]-pre[l-1]){ res = max(res, pre[r]-pre[l-1]); r++; lp = r+1; rp = l+n-1; } } cout << res << "\n"; return 0; }

Compilation message (stderr)

2014_ho_t3.cpp: In function 'll ternary(int, int)':
2014_ho_t3.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...