Областная олимпиада по информатике 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 )
посмотреть в олимпиаде

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

  0
2021-02-21 12:09:35.0 #

#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;

}

  0
2021-02-21 17:59:58.0 #

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

  0
2021-02-23 11:05:55.0 #

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