제출 #952221

#제출 시각아이디문제언어결과실행 시간메모리
952221nguyennhBigger segments (IZhO19_segments)C++14
13 / 100
35 ms2392 KiB
#include<bits/stdc++.h> #define el '\n' using namespace std ; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); const int64_t inf = 1e18; const int MN = 5e5 + 5; int a[MN] , n; namespace sub_trau{ int x[25] , ans = 0; void backtrack(int k){ if (k > n - 1){ int cur = 0 , sum = 0 , cnt = 0; bool check = true; for ( int i = 1 ; i <= n; i++ ){ sum += a[i]; if (x[i] == 1){ if (sum < cur){ check = false; break; } cnt++; cur = sum; sum = 0; } } if (check) ans = max(ans , cnt); return; } for ( int i = 0 ; i <= 1 ; i++ ){ x[k] = i; backtrack(k + 1); } } void solve(){ x[n] = 1; backtrack(1); cout << ans; } } namespace sub2{ void solve(){ vector<int64_t> pref(n + 5); vector<bool> is_greater(n + 5 , false); deque<int> dq; for ( int i = 1 ; i <= n ; i++ ){ while (!dq.empty() && dq.back() <= a[i]) dq.pop_back(); if (dq.size() && dq.front() > a[i]) is_greater[i] = true; dq.push_back(a[i]); } for ( int i = 1 ; i <= n ; i++ ) pref[i] = pref[i - 1] + a[i]; vector<vector<int64_t>> dp(n + 5 , vector<int64_t>(n + 5)); for ( int i = 1 ; i <= n ; i++ ){ for ( int j = i - is_greater[i] ; j >= 1 ; j-- ){ int l = 0 , r = j , pos = -1; while (l <= r){ int mid = l + r >> 1; if (pref[j - 1] - pref[mid - 1] <= pref[i] - pref[j - 1]){ pos = mid; r = mid - 1; } else l = mid + 1; } assert(pos != -1); for ( int k = pos ; k <= j - 1 ; k++ ) { if (is_greater[j - 1] && k == j - 1) continue; dp[i][j] = max(dp[i][j] , dp[j - 1][k] + 1); } } } int64_t ans = 0; for ( int i = 1 ; i <= n ; i++ ){ ans = max(ans , dp[n][i]); } cout << ans; } } int32_t main (){ // freopen("segments.inp" , "r" , stdin); // freopen("segments.out" , "w" , stdout); ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for ( int i = 1 ; i <= n ; i++ ) cin >> a[i]; if (n <= 20){ sub_trau::solve(); return 0; } if (n <= 3000){ sub2::solve(); return 0; } }

컴파일 시 표준 에러 (stderr) 메시지

segments.cpp: In function 'void sub2::solve()':
segments.cpp:63:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |           int mid = l + r >> 1;
      |                     ~~^~~
#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...