Submission #94155

#TimeUsernameProblemLanguageResultExecution timeMemory
94155MrTEKNizin (COCI16_nizin)C++14
100 / 100
99 ms12128 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int,int> ii; const int N = 1e6 + 5; int n,a[N]; ll pre[N]; ll get(int l,int r) { return pre[r] - pre[l - 1]; } int f(int l,int r) { if (l >= r) return 0; for (int i = l ; i < r ; i++) { ll temp = get(l,i); int sl = i + 1, sr = r; while(sl < sr) { int mid = (sl + sr - 1) / 2; if (get(mid,r) > temp) sl = mid + 1; else sr = mid; } if (get(sl,r) == temp) return i - l + r - sl + f(i + 1,sl - 1); } return r - l; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1 ; i <= n ; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; } cout << f(1,n); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...