제출 #497373

#제출 시각아이디문제언어결과실행 시간메모리
497373IerusBigger segments (IZhO19_segments)C++17
0 / 100
1 ms332 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize ("unroll-loops,Ofast,O3") #pragma GCC target("avx,avx2,fma") #define F first #define S second #define int long long #define sz(x) (int)x.size() #define pb push_back #define eb emplace_back #define all(x) (x).begin(),(x).end() const int E = 5e5+777; const long long inf = 1e18+777; const int N = 3e3+777; const int MOD = 1e9+7; int n, a[E], pref[E], dp[E], w[E]; int get(int l, int r){ if(l == -1 || r == -1) return -inf; return pref[r] - pref[l-1]; } signed main(){ ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0); cin >> n; for(int i = 1; i <= n; ++i){ cin >> a[i]; pref[i] = pref[i-1] + a[i]; } int ans = 1, last = a[1]; for(int i = 2; i <= n; ++i){ int L = 1, R = n, res = -1; while(L <= R){ int M = (L + R) >> 1LL; if(last <= get(i, M)){ R = (res = M) - 1; }else L = M + 1; } if(last <= get(i, res)){ ++ans; }else break; int k = i; for(; k < res; ++k){ if(last + k <= get(k+1, res)){ last += k; }else break; } last = get(k, res); i = res; } cout << ans; }
#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...