Submission #959372

#TimeUsernameProblemLanguageResultExecution timeMemory
959372PringBigger segments (IZhO19_segments)C++17
37 / 100
3 ms720 KiB
#include <bits/stdc++.h> using namespace std; #ifdef MIKU string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m"; #define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x) void dout() { cout << dbrs << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif // #define int long long #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++) typedef pair<int, int> pii; using ll = long long; const int MXN = 3005; int n, a[MXN]; int dp[MXN]; ll bnd[MXN], pre[MXN]; void DP(int id) { for (int l = id - 1; true; l--) { ll now = pre[id] - pre[l]; if (now >= bnd[l]) { bnd[id] = now; dp[id] = dp[l] + 1; return; } } } void miku() { cin >> n; assert(n <= 3000); FOR(i, 1, n + 1) cin >> a[i]; FOR(i, 1, n + 1) pre[i] = pre[i - 1] + a[i]; FOR(i, 1, n + 1) DP(i); cout << dp[n] << '\n'; } int32_t main() { cin.tie(0) -> sync_with_stdio(false); cin.exceptions(cin.failbit); miku(); 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...