제출 #486850

#제출 시각아이디문제언어결과실행 시간메모리
486850SirCovidThe19thBigger segments (IZhO19_segments)C++17
0 / 100
1 ms204 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second int n; ll pre[500005]; pair<int, ll> bst, dp[500005]; int main(){ int n; cin >> n; for (int i = 1; i <= n; i++) cin >> pre[i], pre[i] += pre[i - 1]; for (int i = 1, l = 0; i <= n; i++){ while (l < i and pre[i] - pre[l] >= dp[l].s){ bst = max(bst, {dp[l].f + 1, l}); l++; } dp[i] = {bst.f, pre[i] - pre[bst.s]}; } cout<<dp[n].f<<endl; }
#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...