Submission #4282952


Source Code Expand

Copy
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include <map>
#include <fstream>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <assert.h>
#include <complex>
using namespace std;
#define eps 0.000001
#define LONG_INF 10000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define seg_size 65536*16
#define REP(i,n) for(long long i = 0;i < n;++i)
int cost[11] = { 100,2,5,5,4,5,6,3,7,6 };
int ok[11] = {};
pair<long long, long long> dp[20000];
int main() {
	int n, m;
	cin >> n >> m;
	REP(i, m) {
		int a;
		cin >> a;
		ok[a] = 1;
	}
	for (int i = 0; i < 20000; ++i) {
		dp[i] = make_pair(-1, 0);
	}
	dp[0] = make_pair(0,0);
	for (int i = 0; i < n; ++i) {
		if (dp[i].first != -1) {
			for (int t = 1; t <= 9; ++t) {
				if (ok[t] == 1) {
					int next = i + cost[t];
					if (dp[next].first < dp[i].first + 1) {
						dp[next] = make_pair(dp[i].first + 1, t);
					}else if (dp[next].first == dp[i].first + 1) {
						if (dp[next].second < t) {
							dp[next].second = t;
						}
					}
				}
			}
		}
	}
	while (n != 0) {
		cout << dp[n].second;
		n -= cost[dp[n].second];
	}
	cout << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Match Matching
User kotamanegi
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1569 Byte
Status AC
Exec Time 2 ms
Memory 512 KB

Judge Result

Set Name All Sample
Score / Max Score 400 / 400 0 / 0
Status
AC × 29
AC × 3
Set Name Test Cases
All 0_random_1, 0_random_2, 0_random_3, 0_random_4, 0_random_5, 0_random_6, 0_random_7, 0_random_8, 1_normal_1, 1_normal_2, 1_normal_3, 1_normal_4, 1_normal_5, 1_normal_6, 2_corner_1, 2_corner_2, 2_corner_3, 2_corner_4, 2_corner_5, 2_corner_6, 3_hand_1, 3_hand_2, 3_hand_3, 3_hand_4, 3_hand_5, 3_hand_6, sample_01, sample_02, sample_03
Sample sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
0_random_1 AC 1 ms 512 KB
0_random_2 AC 1 ms 512 KB
0_random_3 AC 1 ms 512 KB
0_random_4 AC 2 ms 512 KB
0_random_5 AC 1 ms 512 KB
0_random_6 AC 1 ms 512 KB
0_random_7 AC 1 ms 512 KB
0_random_8 AC 1 ms 512 KB
1_normal_1 AC 1 ms 512 KB
1_normal_2 AC 1 ms 512 KB
1_normal_3 AC 1 ms 512 KB
1_normal_4 AC 2 ms 512 KB
1_normal_5 AC 2 ms 512 KB
1_normal_6 AC 1 ms 512 KB
2_corner_1 AC 1 ms 512 KB
2_corner_2 AC 1 ms 512 KB
2_corner_3 AC 1 ms 512 KB
2_corner_4 AC 1 ms 512 KB
2_corner_5 AC 1 ms 512 KB
2_corner_6 AC 1 ms 512 KB
3_hand_1 AC 1 ms 512 KB
3_hand_2 AC 1 ms 512 KB
3_hand_3 AC 1 ms 512 KB
3_hand_4 AC 1 ms 512 KB
3_hand_5 AC 1 ms 512 KB
3_hand_6 AC 2 ms 512 KB
sample_01 AC 1 ms 512 KB
sample_02 AC 1 ms 512 KB
sample_03 AC 1 ms 512 KB