이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
using namespace std;
//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 gen(time(0));
#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long
const int N = 5e5 + 100;
const int M = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;
ll pref[N];
int a[N];
vector < pair < int, ll > > add[N];
set < pair < int, ll > > st;
pair < int, ll > dp[N];
void upd(pair < int, ll > &a, pair < int, ll > b)
{
if (a.F < b.F) a = b;
else if (a.F == b.F) a.S = min(a.S, b.S);
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif // LOCAL
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i];
if (i) pref[i] = pref[i - 1];
pref[i] += a[i];
}
dp[0] = {1, a[0]};
for(int i = 0; i < n; i++)
{
dp[i] = {1, pref[i]};
if (i) dp[i] = {dp[i - 1].F, dp[i - 1].S + a[i]};
for(int j = i - 1; j >= 0; j--)
{
if (pref[i] - pref[j] < dp[j].S) continue;
for(int z = j; z < i; z++)
{
if (pref[i] - pref[z] < dp[j].S + pref[z] - pref[j]) break;
upd(dp[i], {dp[j].F + 1, pref[i] - pref[z]});
}
break;
}
}
cout << dp[n - 1].F;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |