Submission #521578

#	Time	Username	Problem	Language	Result	Execution time	Memory
521578		TranGiaHuy1508	Bigger segments (IZhO19_segments)	C++17	13 / 100	1 ms	316 KiB

segments

/*

	Unknown's C++ Template (v2)

*/

// Include all standard headers

#include "bits/stdc++.h"
using namespace std;

// Policy-based data structures

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <class A>
using ordered_set = tree<A, null_type, less<A>, rb_tree_tag, tree_order_statistics_node_update>;

template <class A, class B>
using ordered_map = tree<A, B, less<A>, rb_tree_tag, tree_order_statistics_node_update>;

template <class A, class B, class C>
using hashtable = gp_hash_table<A, B, C>;

// AtCoder library

const int ACL = 0;
#if ACL
	#include <atcoder/all>
	using namespace atcoder;
#endif

// Pragmas

const int USE_PRAGMA = 0;
#if USE_PRAGMA
	#pragma GCC optimize("Ofast")
	#pragma GCC optimize("unroll-loops")
	#pragma GCC target("avx,avx2,fma,sse4.2,abm,bmi,bmi2,popcnt")
#endif

// Anti-overflow
#define int long long

// Shortened name

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;

// Macro

#define pb push_back
#define all(x) x.begin(), x.end()
#define ctn continue
#define mid ((l+r)/2)

// Debugging

#ifdef LOCAL
	#define debug(x) cout << #x << " = " << x << "\n";
#else
	#define debug(x) ;
#endif

template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x){
	out << "(" << x.first << ", " << x.second << ")";
	return out;
}

template <class T>
ostream& operator << (ostream& out, vector<T> x){
	out << "[";
	for (int i=0; i<(ll)x.size(); i++){
		if (i) out << ", ";
		out << x[i];
	}
	out << "]";
	return out;
}

// File I/O

void fastio(string finp = "", string fout = ""){
	if (fopen(finp.c_str(), "r")){
		freopen(finp.c_str(), "r", stdin);
		freopen(fout.c_str(), "w", stdout);
	}
}

// Const

const ld PI = acos(-1.0);
const ll allmod[2] = {(ll)1e9+7, 998244353};
const ll mod = allmod[0];
const ll maxn = 2e5;
const ll inf = 1e18;
const ld eps = 1e-6;
const int interactive = 0;
const int multitest = 0;

vi v, pfx;
vii dp;

int getsum(int a, int b){
	return (a > b ? inf : pfx[b] - (a ? pfx[a-1] : 0));
}

void main_program(){
	int n; cin >> n;
	v.resize(n); for (auto &i: v) cin >> i;
	pfx.resize(n);
	for (int i=0; i<n; i++){
		pfx[i] = (i ? pfx[i-1] : 0) + v[i];
	}

	dp.assign(n, {inf, 0});
	for (int i=0; i<n; i++){
		dp[i] = {getsum(0, i), 1};
		int l = 0, r = i-1;

		while (r - l > 1){
			if (dp[mid].first <= getsum(mid + 1, i)) l = mid;
			else r = mid - 1;
		}

		if (l >= 0){
			if (dp[l].first <= getsum(l + 1, i)) dp[i] = min(dp[i], {getsum(l+1, i), dp[l].second + 1});
		}
		if (r >= 0){
			if (dp[r].first <= getsum(r + 1, i)) dp[i] = min(dp[i], {getsum(r+1, i), dp[r].second + 1});
		}
	}

	debug(dp);
	cout << dp[n-1].second;
}

void pre_main(){

}

signed main(){
	#ifdef LOCAL
		auto start_time = chrono::high_resolution_clock::now();
	#endif

	if (!interactive) {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
	#ifndef ONLINE_JUDGE
		fastio(".inp", ".out");
	#endif

	int t = 1;
	if (multitest) cin >> t;
	pre_main();
	while (t--) main_program();

	#ifdef LOCAL
		auto end_time = chrono::high_resolution_clock::now();
		auto duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
		cout << "\n[" << duration << "ms]\n";
	#endif
}

Compilation message (stderr)

segments.cpp: In function 'void fastio(std::string, std::string)':
segments.cpp:96:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   freopen(finp.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:97:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   freopen(fout.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27