Submission #4284697


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;

int cost[9] = {2, 5, 5, 4, 5, 6, 3, 7, 6};

// K桁をN本使ってできたときの先頭の数字の最大
int dp[10101][10101] = {0};
int back[10101][10101] = {0};
bool ok[9] = {0};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a;
    cin >> a;
    ok[a - 1] = true;
  }
  int k = n;
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j <= n; j++)
      dp[i][j] = back[i][j] = -1;
  }
  dp[0][0] = 0;
  for (int i = 0; i < k; i++)
    for (int j = 0; j < n; j++)
      for (int l = 0; l < 9; l++) {
        if (!ok[l] || dp[i][j] < 0)
          continue;
        if (j + cost[l] <= n && dp[i + 1][j + cost[l]] < l) {
          dp[i + 1][j + cost[l]] = l;
          back[i + 1][j + cost[l]] = j;
        }
      }
  int now = n;
  while (dp[now][n] < 0)
    now--;
  int from = n;
  while (now > 0) {
    cout << dp[now][from] + 1;
    from = back[now][from];
    now--;
  }
  cout << endl;
  return 0;
}

Submission Info

Submission Time
Task D - Match Matching
User ninja7
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1232 Byte
Status AC
Exec Time 1583 ms
Memory 792832 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 3 ms 8704 KB
0_random_2 AC 2 ms 2432 KB
0_random_3 AC 110 ms 185216 KB
0_random_4 AC 1420 ms 776448 KB
0_random_5 AC 1505 ms 792832 KB
0_random_6 AC 1474 ms 792832 KB
0_random_7 AC 742 ms 552832 KB
0_random_8 AC 65 ms 135936 KB
1_normal_1 AC 338 ms 357760 KB
1_normal_2 AC 1304 ms 743680 KB
1_normal_3 AC 312 ms 339200 KB
1_normal_4 AC 945 ms 618496 KB
1_normal_5 AC 1036 ms 659584 KB
1_normal_6 AC 516 ms 452224 KB
2_corner_1 AC 185 ms 255104 KB
2_corner_2 AC 19 ms 57984 KB
2_corner_3 AC 912 ms 616448 KB
2_corner_4 AC 80 ms 154496 KB
2_corner_5 AC 12 ms 39424 KB
2_corner_6 AC 244 ms 298240 KB
3_hand_1 AC 1462 ms 792832 KB
3_hand_2 AC 2 ms 2432 KB
3_hand_3 AC 2 ms 2304 KB
3_hand_4 AC 2 ms 4480 KB
3_hand_5 AC 2 ms 2304 KB
3_hand_6 AC 1583 ms 792832 KB
sample_01 AC 2 ms 2432 KB
sample_02 AC 3 ms 8704 KB
sample_03 AC 2 ms 2432 KB