# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
473253 | Lam_lai_cuoc_doi | Bigger segments (IZhO19_segments) | C++17 | 3 ms | 1344 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define task "PARTITION"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using ld = long double;
template <class T>
void read(T &x)
{
x = 0;
register int c;
while ((c = getchar()) && (c > '9' || c < '0'))
;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
}
constexpr int N = 5e5 + 5;
constexpr int Inf = 1e9 + 7;
int n;
ll a[N];
void Read()
{
cin >> n;
//read(n);
for (int i = 1; i <= n; ++i)
cin >> a[i];
//read(a[i]);
//reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i)
a[i] += a[i - 1];
}
void Sub_1()
{
vector<vector<int>> dp(n + 5, vector<int>(n + 5, -Inf));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = i - 1, t = i - 2; j >= 0; --j)
{
if (t >= j)
--t;
while (t >= 0 && a[i] - a[j] >= a[j] - a[t])
--t;
dp[i][j] = max(dp[i][j + 1], dp[j][t + 1] + 1);
}
}
cout << dp[n][0];
}
void Greedy()
{
ll pre(0);
ll now(0);
int ans(0);
for (int i = 1; i <= n;)
{
++ans;
do
{
now += a[i] - a[i - 1];
++i;
} while (i <= n && now < pre);
if (now < pre)
break;
pre = now;
now = 0;
}
cout << ans;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen(task ".INP", "r"))
{
freopen(task ".INP", "r", stdin);
freopen(task ".OUT", "w", stdout);
}
Read();
if (n <= 1000)
Sub_1();
else
Greedy();
}
Compilation message (stderr)
# | 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... |