제출 #769945

#제출 시각아이디문제언어결과실행 시간메모리
769945JomnoiBigger segments (IZhO19_segments)C++17
37 / 100
4 ms408 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 3005; const long long INF = 1e18 + 7; long long A[MAX_N], dp1[MAX_N], dp2[MAX_N]; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N; cin >> N; for (int i = 1; i <= N; i++) cin >> A[i]; for (int i = 1; i <= N; i++) dp1[i] = dp2[i] = INF; for (int i = 1; i <= N; i++) { long long sum = 0; for (int j = i; j >= 1; j--) { sum += A[j]; if (dp1[j - 1] <= sum) { dp1[i] = sum; dp2[i] = dp2[j - 1] + 1; break; } } } cout << dp2[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...