제출 #1198446

#제출 시각아이디문제언어결과실행 시간메모리
1198446TheSahibBigger segments (IZhO19_segments)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; using int64 = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int64> a(N); for(int i = 0; i < N; i++){ cin >> a[i]; } // 1) compute prefix sums S[0..N] vector<int64> S(N+1, 0); for(int i = 1; i <= N; i++){ S[i] = S[i-1] + a[i-1]; } // 2) best[d] = smallest prefix-sum at which we can form d segments const int64 INF = (int64)4e18; // we need up to N+1 entries vector<int64> best(N+2, INF); best[0] = 0; // zero segments at sum 0 int answer = 0; // 3) for each position i, find max d with best[d] <= S[i] for(int i = 1; i <= N; i++){ int lo = 0, hi = i; // binary search for largest d in [0..i] with best[d] <= S[i] while(lo < hi){ int mid = (lo + hi + 1) >> 1; if(best[mid] <= S[i]) lo = mid; else hi = mid - 1; } int d = lo; answer = max(answer, d); // update best[d+1] if(best[d+1] > S[i]){ best[d+1] = S[i]; } } cout << answer << "\n"; return 0; }
#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...