oj.uz

답안 #845156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
845156 2023-09-06T12:20:53 Z Piokemon Table Tennis (info1cup20_tabletennis) C++17
20 / 100
 1144 ms 1048580 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];
	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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 772 ms 949188 KB Output is correct
2 Correct 694 ms 949328 KB Output is correct
3 Correct 694 ms 949268 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 720 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1144 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 202220 KB Output is correct
2 Runtime error 514 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 201960 KB Output is correct
2 Runtime error 1 ms 720 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 529 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -