235392026-01-24 12:38:37BalimeWalking In The Parkcpp17Wrong answer 0/100463ms22668 KiB
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ll n,m,k; cin>>n>>m>>k;

	map<ll,ll> ma;

	vector<ll> a(n+1), b(m+1), a2(n+1);
	ll par[200001];
	for(ll i=1; i<=n; i++)
	{
		cin>>a[i];
		a[i]+=a[i-1];
	}
	for(ll i=1; i<=m; i++)
	{
		cin>>b[i];
		b[i]+=b[i-1];
		ma.insert({b[i], i});
	}
	for(ll i=0; i<=n; i++)
	{
		if(ma.find(a[i])!=ma.end())a2[i]=ma[a[i]];
		else a2[i]=INT_MAX;
	}
	vector<ll> lis;
	vector<ll> top;
	for(ll i=0; i<=n; i++)
	{
		auto it =upper_bound(lis.begin(), lis.end(), a2[i]);
		if(it==lis.end())
		{
			lis.push_back(a2[i]);
			top.push_back(i);
			if(lis.size()>1)
			{
				par[i]=top[lis.size()-2];
			}
			else {
				par[i]=0;
			}
		}
		else 
		{
			*it=a2[i];
			top[it-lis.begin()]=i;
			if(it-lis.begin()-1>=0)par[i]=top[it-lis.begin()-1];
			else par[i]=0;
		}
	}
	/*for(ll i=0; i<=n+1; i++)
	{
		cout<<par[i]<<" ";
	}cout<<endl;*/

	if(lis.size()<k){
		cout<<-1<<endl; return 0;
	}

	ll h=par[n];

	if(a[n]!=b[m]){
		cout<<-1<<endl; return 0;
	}
	stack<ll> st;
	for(ll i=1; i<k; i++)
	{
		st.push(h);
		h=par[h];
	}
	if(st.size()<k-1)
	{
		cout<<-1<<endl;
		return 0;
	}
	cout<<endl;
	h=par[n];
	for(ll i=1; i<k; i++)
	{
		st.push(a2[h]);
		h=par[h];
	}
	while(!st.empty())
	{
		cout<<st.top()<<" ";st.pop();
	}

}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer1ms316 KiB
2Wrong answer1ms316 KiB
subtask20/19
3Wrong answer287ms22376 KiB
4Wrong answer284ms22364 KiB
5Wrong answer298ms22380 KiB
6Wrong answer293ms22620 KiB
7Wrong answer298ms22420 KiB
8Accepted284ms22164 KiB
9Wrong answer303ms22668 KiB
subtask30/23
10Wrong answer1ms500 KiB
11Wrong answer1ms316 KiB
12Wrong answer1ms316 KiB
13Wrong answer1ms316 KiB
14Accepted1ms316 KiB
15Wrong answer1ms316 KiB
subtask40/16
16Wrong answer2ms316 KiB
17Wrong answer2ms316 KiB
18Wrong answer3ms316 KiB
19Wrong answer3ms316 KiB
20Wrong answer2ms316 KiB
21Accepted2ms316 KiB
22Wrong answer2ms316 KiB
subtask50/42
23Wrong answer463ms20840 KiB
24Wrong answer421ms20852 KiB
25Wrong answer425ms20896 KiB
26Wrong answer463ms21144 KiB
27Wrong answer405ms21216 KiB
28Accepted462ms20640 KiB
29Wrong answer458ms21408 KiB