Submission #977276

#TimeUsernameProblemLanguageResultExecution timeMemory
977276colossal_pepeBigger segments (IZhO19_segments)C++17
37 / 100
169 ms262144 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int n; vector<ll> a; ll solve() { vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0)); for (int i = n; i >= 1; i--) { for (int j = i; j <= n; j++) { auto itr = lower_bound(a.begin(), a.end(), 2 * a[j] - a[i - 1]); if (itr == a.end()) dp[i][j] = 1; else dp[i][j] = 1 + dp[j + 1][itr - a.begin()]; } for (int j = n - 1; j >= i; j--) { dp[i][j] = max(dp[i][j], dp[i][j + 1]); } } return dp[1][1]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; a.resize(n + 1, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] += a[i - 1]; } cout << solve() << '\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...