Submission #845156

#	Time	Username	Problem	Language	Result	Execution time	Memory
845156		Piokemon	Table Tennis (info1cup20_tabletennis)	C++17	20 / 100	1144 ms	1048580 KiB

tabletennis

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int a[2137];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin >> n >> k;
	for (int x=1;x<=n+k;x++) cin >> a[x];
	vector<int> dp[n+k+9][n+k+9][k+9];
	dp[1][n+k][0].push_back(0);
	int wybr = -1;
	for (int x=1;x<=n+k;x++){
		for (int y=n+k;y>=x;y--){
			for (int z=0;z<=k;z++){
				for (int w:dp[x][y][z]){
					if (w==0) dp[x+1][y-1][z].push_back(a[x]+a[y]);
					if (w==a[x]+a[y]) dp[x+1][y-1][z].push_back(w);
					if (z<k){
						dp[x+1][y][z+1].push_back(w);
						dp[x][y-1][z+1].push_back(w);
					}
				}
			}
		}
	}
	/*for (int x=1;x<=n+k;x++){
		for (int y=1;y<=n+k;y++){
			for (int z=0;z<=k;z++){
				if (dp[x][y][z].empty())continue;
				cout << x << ' ' << y << ' ' << z << ": ";
				for (int w:dp[x][y][z]) cout << w << ' ';
				cout << '\n';
			}
		}
	}*/
	for (int x=1;x<n+k;x++){
		for (int w:dp[x+1][x][k]){
			wybr=w;
			break;
		}
	}
	//cout << "wybr: " << wybr << '\n';
	vector<int> odp;
	map<int,int> cnt;
	for (int x=1;x<=n+k;x++) cnt[a[x]]++;
	int zost=n;
	for (int x=1;x<=n+k;x++){
		if (zost==0) break;
		if (cnt[a[x]]>0 && cnt[wybr-a[x]]>0){
			cnt[a[x]]--;
			cnt[wybr-a[x]]--;
			odp.push_back(a[x]);
			odp.push_back(wybr-a[x]);
			zost-=2;
		}
	}
	//cout << "odp" << '\n';
	sort(odp.begin(),odp.end());
	for (int x:odp) cout << x << ' ';
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 9 / 9
• Subtask 6: 0 / 14
• Subtask 7: 0 / 15
• Subtask 8: 0 / 13