Submission #467024

#TimeUsernameProblemLanguageResultExecution timeMemory
467024TeaTimeBigger segments (IZhO19_segments)C++17
0 / 100
1 ms204 KiB
//#pragma GCC optimize("O3") //#pragma GCC target("avx2") #include <iostream> #include <vector> #include <string> #include <algorithm> #include <map> #include <set> #include <queue> #include <unordered_map> #include <cmath> using namespace std; #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); typedef long long ll; typedef long double ld; const ll SZ = 1e6 + 100, INF = 1e9, AM = 2, K = 26; pair<ll, ll> dp[SZ]; ll n; vector<ll> vec; signed main() { fastInp; cin >> n; vec.resize(n); vector<ll> pref(1); for (auto& c : vec) { cin >> c; pref.push_back(pref.back() + c); } ll i2 = 0; dp[1] = { 1, vec[0] }; ll ans = 1; for (int i = 2; i <= n; i++) { while (i2 + 1 != i && (dp[i2].first < dp[i - 1].first - 1 || pref[i] - pref[i2 + 1] >= dp[i2 + 1].second)) { i2++; } dp[i].second = pref[i] - pref[i2]; dp[i].first = dp[i2].first + 1; ans = max(ans, dp[i].first); } cout << ans; 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...