Submission #959384

#TimeUsernameProblemLanguageResultExecution timeMemory
959384PringBigger segments (IZhO19_segments)C++17
0 / 100
2 ms2512 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++) using ll = long long; typedef pair<int, int> pii; typedef pair<ll, int> pli; const int MXN = 500005; int n, a[MXN]; int dp[MXN]; ll pre[MXN]; multiset<pli> MS; 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; // break; // } // } // FOR(l, 0, id) { // cout << (pre[id] - pre[l] >= bnd[l]) << ' '; // } // cout << '\n'; auto it = MS.upper_bound(mp(pre[id], id)); int l = prev(it) -> sc; dp[id] = dp[l] + 1; MS.insert(mp(pre[id] - pre[l] + pre[id], id)); } 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]; MS.insert(mp(0LL, 0)); 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...