Submission #344011

#TimeUsernameProblemLanguageResultExecution timeMemory
344011IZhO_2021_I_want_SilverBigger segments (IZhO19_segments)C++14
100 / 100
97 ms20972 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx") #include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> #include <map> #include <iomanip> #include <cassert> #include <stack> #include <queue> #include <deque> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp>- using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; // template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // order_of_key (k) : Number of items strictly smaller than k . // find_by_order(k) : K-th element in a set (counting from zero). #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define pb push_back #define ppb pop_back #define mkp make_pair #define F first #define S second #define lb lower_bound #define ub upper_bound #define show(a) cerr << #a <<" -> "<< a <<" " #define nl cerr <<"\n" #define int ll const int N = 5e5 + 5; const int oo = 1e15 + 5; int n, a[N], sum[N], dp[N], ind[N]; void solve() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; sum[i] = sum[i-1] + a[i]; } ind[1] = 0; for (int j = 1; j <= n; ++j) { // sum[j] - sum[k] <= sum[i] - sum[j] // ind[j] -> k <= j <= bin_search -> i // sum[j] + sum[j] - sum[ind[j]]] <= sum[i] // ind[i] = max(j, ind[1, 2, ..., i-1]) ind[j] = max(ind[j-1], ind[j]); dp[j] = max(dp[j-1], dp[ind[j]] + 1); int l = 1, r = n; while (l < r) { int mid = (l + r) / 2; if (sum[j] + sum[j] - sum[ind[j]] <= sum[mid]) r = mid; else l = mid + 1; } if (sum[j] + sum[j] - sum[ind[j]] <= sum[r]) { ind[r] = j; } } //for (int i = 1; i <= n; ++i) { show(i); show(ind[i]); nl;} cout << dp[n]; } /*7 5 1 4 5 3 9 9 */ main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int tests = 1; //cin >> tests; while (tests --) { solve(); } return 0; } /* Just Chalish! */

Compilation message (stderr)

segments.cpp:73:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 |  main () {
      |        ^
#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...