Submission #421910

#	Time	Username	Problem	Language	Result	Execution time	Memory
421910		juancarlovieri	Sequence (BOI14_sequence)	C++17	67 / 100	1072 ms	2280 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define int long long

int ans = 1000000000000000000;
int pw[20];

void rek(vector<int> sections, int curr = 0, int level = 0, bool flag = false) {
  if (curr >= ans) return;
  int n = sections.size();

  if (n == 1) {
    int mask = sections[0];
    if (!mask) {
      if (!curr || flag) curr += pw[level];
    } else if (mask == 1) curr += pw[level + 1];
    else {
      if (mask & 1) {
        int mn = 10;
        for (int i = 9; i; --i) {
          if (mask & (1 << i)) mn = i;
        }
        for (int i = 9; i; --i) {
          if ((mask & (1 << i)) && i != mn) curr += i * pw[level++];
        }
        curr += mn * pw[++level];
      } else {
        for (int i = 9; i; --i) {
          if (mask & (1 << i)) curr += i * pw[level++];
        }
      }
    }
    ans = min(ans, curr);
    return;
  }

  for (int i = 0; i < 10; ++i) {
    vector<int> merged;
    int ins = 0;
    bool zero = false;
    int piv = i;
    for (int j = 0; j < n; ++j) {
      zero |= (piv == 0 && (sections[j] & 1));
      ins |= (sections[j] & (~(1 << piv)));
      piv++;
      if (piv == 10) {
        merged.push_back(ins);
        ins = piv = 0;
      }
    }
    if (piv) merged.push_back(ins);
    rek(merged, curr + pw[level] * i, level + 1, zero);
  }
}

signed main() {
  int n;
  cin >> n;
  vector<int> sections(n);
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    sections[i] = (1 << x);
  }
  pw[0] = 1;
  for (int i = 1; i < 18; ++i) pw[i] = 10 * pw[i - 1];
  rek(sections);
  cout << ans << endl;
}

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 0 / 33