제출 #475401

#제출 시각아이디문제언어결과실행 시간메모리
475401ismoilovBigger segments (IZhO19_segments)C++14
13 / 100
1 ms204 KiB
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; #define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); void S() { int n; cin >> n; vector <ll> a(n+2), dp(n+2), pr(n+2); vector <int> best(n+2); for(int i = 1; i <= n; i ++){ cin >> a[i]; pr[i] = pr[i-1] + a[i]; } for(int i = 1; i <= n; i ++){ best[i] = max(best[i], best[i-1]); dp[i] = dp[best[i]] + 1; int cur = pr[i] * 2 - pr[best[i]]; int x = lower_bound(pr.begin()+1, pr.begin()+n+1, cur) - pr.begin(); best[x] = max(best[x], i); } cout << dp[n]; } int main() { IOS; /*int t; cin >> t; while(t --)*/ S(); }
#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...