oj.uz

Submission #845187

# Submission time Handle Problem Language Result Execution time Memory
845187 2023-09-06T12:30:07 Z Piokemon Table Tennis (info1cup20_tabletennis) C++17
35 / 100
 790 ms 1048576 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 330464 KB Output is correct
2 Correct 790 ms 440464 KB Output is correct
3 Correct 785 ms 440192 KB Output is correct
4 Correct 771 ms 440028 KB Output is correct
5 Correct 779 ms 440400 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Runtime error 548 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2908 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 509 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -