제출 #845187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
845187		Piokemon	Table Tennis (info1cup20_tabletennis)	C++17	35 / 100	790 ms	1048576 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];
	if (k==1){
		for (int pomin=1;pomin<=n+k;pomin++){
			int l=1,r=n+k;
			bool ok=1;
			int suma=0;
			while(l<r){
				if (l==pomin)l++;
				if (r==pomin)r--;
				if (suma==0) suma=a[l]+a[r];
				if (suma!=a[l]+a[r]) ok=0;
				l++;
				r--;
			}
			if (ok){
				for (int x=1;x<=n+k;x++){
					if (x!=pomin) cout << a[x] << ' ';
				}
				cout << '\n';
				return 0;
			}
		}
	}
	set<int> dp[n+k+9][n+k+9][k+9];
	dp[1][n+k][0].insert(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].insert(a[x]+a[y]);
					if (w==a[x]+a[y]) dp[x+1][y-1][z].insert(w);
					if (z<k){
						dp[x+1][y][z+1].insert(w);
						dp[x][y-1][z+1].insert(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: 15 / 15
• Subtask 5: 9 / 9
• Subtask 6: 0 / 14
• Subtask 7: 0 / 15
• Subtask 8: 0 / 13