Областная олимпиада по информатике 2020 год, 9-11 классы

Задача D. Разделение массива

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

У Тимы есть три младших брата: Батыр, Димаш и Есмахан. Тима решил дать им массив $a$ из $n$ целых чисел, чтобы развлечь их. Он хочет разделить массив на три непустых частей и раздать своим братьям, чтобы каждое число было ровно в одной части. Все числа одной части должны идти подряд в массиве. Пусть $A$ - сумма чисел в первой части, $B$ - сумма чисел во второй, $C$ - сумма в третьей. Чтобы братья не ругались, Тима хочет минимизировать max(A, B, C) - min(A, B, C). Найдите минимальное значение max(A, B, C) - min(A, B, C).

Формат входного файла

В первой строке дано одно целое число $n$ $(3 <= n <= 3 * 10^5)$. Во второй строке дано $n$ целых чисел $a_1$, $a_2$, $\dots$, $a_n$ $(0 <= a_i <= 10^5)$.

Формат выходного файла

Выведите одно целое число — ответ на задачу.

Система оценки

Это задача состоит из 4 подзадач и 20 тестов, каждый тест оценивается в 5 баллов:

1. $n <= 10^2$. Тесты 1 -- 4
2. $n <= 5 * 10^3$. Тесты 5 -- 8
3. $a_i <= 1$. Тесты 9 -- 12
4. $n <= 3 * 10^5$. Тесты 13 -- 20

Пример:

Вход

7
4 1 2 3 1 3 2

Ответ

1

Замечание

Один из вариантов разделении в примере: 4 1 | 2 3 1 | 3 2 Также можно разделить 4 1 | 2 3 | 1 3 2 ( Aibar Kuanyshbay )

Комментарий/решение

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

int k = 0;

int a[n];

for(int i=0;i<n;i++) {

cin >> a[i];

k += a[i];

}

cout << k%3;

return 0;

}

неправильный тест 3

показать/скрыть код

#include <bits/stdc++.h>
#include <algorithm>
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define N 300010
#define pb push_back
#define fi first
#define se second
#define si size()
#define ll long long
#define mp make_pair
#define iter ::iterator
#define all(v) v.begin(), v.end()
#define READ(f) freopen (f, "r", stdin)
#define WRITE(f) freopen (f, "w", stdout)
#define mapiter map<int, int>::iterator
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forn1(i, n) for(int i = 1; i <= n; ++i)
#define forr(i, n) for(int i = n - 1; i >= 0; --i)
#define forr1(i, n)	for(int i = n; i >= 1; --i)
#define barnarnar ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define elif else if
#define lld long double
#define r0 return 0
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int inf = 6e3;
const ll infl = 2e17;
const ll modw = 1000000007ll;

const ll mods[2] = {1000000009ll, 1000000007ll};
const ll pp[2] = {31, 53};
const int K = 180;
const int KN = 710;
const int LG = 17;

using namespace std;
//using namespace __gnu_pbds;

ll binpow(ll a1, ll n1)
{
	if(n1 == 0)	return 1ll;
	if(n1 & 1ll)	return (binpow(a1, n1 - 1) * a1);
	else
	{
		ll b1 = binpow(a1, n1 >> 1ll);
		return (b1 * b1);
	}
}

ll a[N];
ll pr[N];

ll calc(ll a, ll b, ll c)
{
	return max(a, max(b, c)) - min(a, min(b, c));
}

ll get(ll l, ll r)
{
	return pr[r] - pr[l - 1];
}

void solve()
{
	int n;
	cin >> n;
	forn1(i, n)
	{
		cin >> a[i];
		pr[i] = pr[i - 1] + a[i];
	}
	ll s = 0;
	ll ans = infl;
	forn1(i, n - 2)
	{
		s += a[i];
		ll l = i + 1, r = n - 1;
		int j = 69;
		while(j--)
		{
			ll m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
			if(calc(s, get(i + 1, m1), get(m1 + 1, n)) > calc(s, get(i + 1, m2), get(m2 + 1, n)))	l = m1;
			else	r = m2;
		}
		while(r >= l)
		{
			ans = min(ans, calc(s, get(i + 1, r), get(r + 1, n)));
			r--;
		}
	}
	cout << ans;
	return;
}

int main()
{
	barnarnar
	int tt = 1;
	//cin >> tt;
	while(tt--)
	{
		solve();
	}
    r0;
}
// ._.

показать/скрыть код

#include <iostream>
#include <fstream>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#include <stdio.h>
#include <numeric>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <iterator>
#include <assert.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int MOD = 1e9 + 7; //1073741824;
const int N = 2e6 + 1;
const ll INF = 9e18;
const int M = 2010;
#define ss second
#define ff first
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(a) (int)a.size()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define NDEBUG

ll a[N];
ll pref[N];
ll get(ll a, ll b, ll c) {
    return max({ a, b, c }) - min({ a, b, c });
}
void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pref[i] += pref[i - 1] + a[i];
    }
    ll ans = INF;
    for (int i = 1; i < n - 1; ++i) {
        int l = i + 1, r = n - 1;
        while ((r - l) >= 0) {
            int mid = (r + l) >> 1;
            if (pref[i] >= (pref[mid] - pref[i])) l = mid + 1;
            else r = mid - 1;
        }
        --l;
        l = max(l, i + 1);
        ans = min(ans, get(pref[i], pref[l] - pref[i], pref[n] - pref[l]));
        l = i + 1, r = n - 1;
        while ((r - l) >= 0) {
            int mid = (r + l) >> 1;
            if (pref[i] <= (pref[mid] - pref[i])) r = mid - 1;
            else l = mid + 1;
        }
        ++r;
        r = min(r, n - 1);
        ans = min(ans, get(pref[i], pref[r] - pref[i], pref[n] - pref[r]));
        l = i + 1, r = n - 1;
        while ((r - l) >= 0) {
            int mid = (r + l) >> 1;
            if (pref[i] <= (pref[n] - pref[mid])) l = mid + 1;
            else r = mid - 1;
        }
        --l;
        l = max(l, i + 1);
        ans = min(ans, get(pref[i], pref[l] - pref[i], pref[n] - pref[l]));
        l = i + 1, r = n - 1;
        while ((r - l) >= 0) {
            int mid = (r + l) >> 1;
            if (pref[i] >= (pref[n] - pref[mid])) r = mid - 1;
            else l = mid + 1;
        }
        ++r;
        r = min(r, n - 1);
        ans = min(ans, get(pref[i], pref[r] - pref[i], pref[n] - pref[r]));
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}