ГЖО 7-8 класс 2019 год

Задача D. Лучшие друзья

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

1 секунда

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

256 мегабайт

Айбай и Абар играют игру. У них есть два массива целых положительных чисел $a$ и $b$. Айбай может взять два соседних числа из массива $a$ и заменить их суммой этих двух чисел. Например : $[2, 4, 1, 7]$ -> $[2, 5, 7]$. Абар может делать то же самое с массивом $b$. Так как они лучшие друзья, то они хотят, чтобы получившиеся массивы были одинаковыми. Но они очень любят большие массивы, поэтому они хотят, чтобы получившиеся массивы были еще и максимальной длины. Найдите максимальную возможную длину получившихся массивов.

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

В первой строке задано целое число $n$ $(1 <= n <= 300000)$ - длина первого массива. Во второй строке задано $n$ целых чисел $a_{1},a_{2},...,a_{n}$ $(0 <= a_{i} <= 10^9)$ - элементы массива $a$. В третьей строке задано целое число $m$ $(1 <= m <= 300000)$ - длина второго массива. В четвертой строке задано $m$ целых чисел $b_{1},b_{2},...,b_{m}$ $(0 <= b_{i} <= 10^9)$ - элементы массива $b$.

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

Выведите одно число — максимальную длину полученных массивов после применения операций к массивам $a$ и $b$ таким образом, что они становятся одинаковыми. Если же не существует способа сделать массивы одинаковыми, выведите -1.

Примеры:

Вход

5
11 2 3 5 7
4
11 7 3 7

Ответ

3

Вход

2
1 2
1
100

Ответ

-1

Вход

3
1 2 3
3
1 2 3

Ответ

3

( Batyr Sardarbekov )

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

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

#include <bits/stdc++.h>
#define ll long long
#define N 300010
#define pb push_back
#define si size()

using namespace std;

const int inf = 2e9;

ll a[N], b[N];

int main()
{
    int n;
    cin >> n;
    ll s1 = 0, s2 = 0;
    for(int i = 0; i < n; i++)
    {
    	cin >> a[i];
    	s1 += a[i];
	}
	int m;
	cin >> m;
	for(int i = 0; i < m; i++)
	{
		cin >> b[i];
		s2 += b[i];
	}
	if(s1 != s2)
	{
		cout << -1;
		return 0;
	}
	vector<ll> t1;
	vector<ll> t2;
	t1.pb(a[0]);
	t2.pb(b[0]);
	int pos1 = 1, pos2 = 1;
	while(pos1 < n && pos2 < m)
	{
		ll l1 = t1[t1.si - 1], l2 = t2[t2.si - 1];
		if(l1 == l2)
		{
			t1.pb(a[pos1]);
			t2.pb(b[pos2]);
			pos1++;
			pos2++;
			continue;
		}
		if(l1 > l2)
		{
			t2[t2.si - 1] += b[pos2];
			pos2++;
		}
		else
		{
			t1[t1.si - 1] += a[pos1];
			pos1++;
		}
	}
	cout << t1.size();
}

#include <bits/stdc++.h>

#define yes cout << "Yes\n"

#define no cout << "No\n"

#define Zhussip ios_base::sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr)

#define all(a) (a).begin(),(a).end()

typedef long long ll;

#define int long long

const int maxn = 4e5 + 2008;

const long long inf = 1e18 + 2008;

const int mod = 1e9 + 7;

using namespace std;

int a[maxn], b[maxn], pref[maxn], prefb[maxn], n, m;

int rec(int v, int vb) {

int left = vb + 1;

if (vb >= m || v >= n) return 0;

for (int l = v + 1; l <= n; l++) {

while (prefb[left] - prefb[vb] < pref[l] - pref[v] && left < m) {

left++;

}

if (pref[l] - pref[v] == prefb[left] - prefb[vb]) {

return rec(l, left) + 1;

}

}

return 0;

}

void keepcoding() {

cin >> n;

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

cin >> a[i];

pref[i] = pref[i - 1] + a[i];

}

cin >> m;

for (int i = 1; i <= m; i++) {

cin >> b[i];

prefb[i] = prefb[i - 1] + b[i];

}

if (prefb[m] != pref[n]) {

cout << -1;

return;

}

int ans = rec(0, 0);

cout << ans;

}

signed main() {

Zhussip;

srand(time(0));

int _ = 1;

while (_ > 0) {

keepcoding();

_--;

}

return 0;

}

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

#include <bits/stdc++.h>

#define yes cout << "Yes\n"
#define no cout << "No\n"

#define Zhussip ios_base::sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr)

#define all(a) (a).begin(),(a).end()

typedef long long ll;

#define int long long

const int maxn = 4e5 + 2008;
const long long inf = 1e18 + 2008;
const int mod = 1e9 + 7;

using namespace std;

int a[maxn], b[maxn], pref[maxn], prefb[maxn], n, m;

int rec(int v, int vb) {
	int left = vb + 1;
	if (vb >= m || v >= n) return 0;
	for (int l = v + 1; l <= n; l++) {
		while (prefb[left] - prefb[vb] < pref[l] - pref[v] && left < m) {
			left++;
		}
		if (pref[l] - pref[v] == prefb[left] - prefb[vb]) {
			return rec(l, left) + 1;
		}
	}
	return 0;
}

void keepcoding() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
		prefb[i] = prefb[i - 1] + b[i];
	}
	if (prefb[m] != pref[n]) {
		cout << -1;
		return;
	}
	int ans = rec(0, 0);
	cout << ans;
}

signed main() {
	Zhussip;
	srand(time(0));
	int _ = 1;
	while (_ > 0) {
		keepcoding();
		_--;
	}
	return 0;
}