Submission #4283331


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  V<> c{2, 5, 5, 4, 5, 6, 3, 7, 6};
  V<> a(m); for (int i = 0; i < m; ++i) cin >> a[i], --a[i];
  sort(rbegin(a), rend(a));
  V<> dp(n + 1, -1e9);
  V<> prev(n + 1);
  dp[0] = 0;
  for (int x = 1; x <= n; ++x) {
    for (int i = 0; i < m; ++i) if (x - c[a[i]] >= 0) {
      int curr = dp[x - c[a[i]]] + 1;
      if (curr > dp[x]) {
        dp[x] = curr;
        prev[x] = a[i];
      }
    }
  }
  string res;
  while (n > 0) {
    res += '1' + prev[n];
    n -= c[prev[n]];
  }
  cout << res << '\n';
}

Submission Info

Submission Time
Task D - Match Matching
User risujiroh
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1019 Byte
Status AC
Exec Time 1 ms
Memory 384 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 256 KB
0_random_2 AC 1 ms 256 KB
0_random_3 AC 1 ms 256 KB
0_random_4 AC 1 ms 384 KB
0_random_5 AC 1 ms 384 KB
0_random_6 AC 1 ms 384 KB
0_random_7 AC 1 ms 384 KB
0_random_8 AC 1 ms 256 KB
1_normal_1 AC 1 ms 256 KB
1_normal_2 AC 1 ms 384 KB
1_normal_3 AC 1 ms 256 KB
1_normal_4 AC 1 ms 384 KB
1_normal_5 AC 1 ms 384 KB
1_normal_6 AC 1 ms 256 KB
2_corner_1 AC 1 ms 256 KB
2_corner_2 AC 1 ms 256 KB
2_corner_3 AC 1 ms 384 KB
2_corner_4 AC 1 ms 256 KB
2_corner_5 AC 1 ms 256 KB
2_corner_6 AC 1 ms 256 KB
3_hand_1 AC 1 ms 384 KB
3_hand_2 AC 1 ms 256 KB
3_hand_3 AC 1 ms 256 KB
3_hand_4 AC 1 ms 256 KB
3_hand_5 AC 1 ms 256 KB
3_hand_6 AC 1 ms 384 KB
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 AC 1 ms 256 KB