Submission #1126625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126625		JelalTkm	Sequence (BOI14_sequence)	C++20	0 / 100	1097 ms	13660 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 2e1 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int T = 1;
  // cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];

    vector<int> pw(18);
    pw[0] = 1;
    for (int i = 1; i < 18; i++)
      pw[i] = pw[i - 1] * 10;

    vector<vector<vector<pair<int, set<int>>>>> dp(N, vector<vector<pair<int, set<int>>>> (10, vector<pair<int, set<int>>> (11, pair<int, set<int>> ())));
    for (int i = 0; i < n; i++) {
      for (int j = 1; j < 18; j++) {
        for (int k = 0; k < 10; k++) {
          if (j == 1) {
            dp[j][k][10].first = k;
            if ((k + i) % 10 == a[i]) {
              dp[j][k][10].second.insert(i);
            }
          } else {
            for (int k1 = 0; k1 < 10; k1++) {
              if (j == 2 && k1 == 0 && k == 0)
                continue;
              set<int> s1 = dp[j][k][k1].second;
              if (dp[j - 1][k1][10].second.find(i) != dp[j - 1][k1][10].second.end())
                s1.insert(i);
              if ((((k * pw[j - 1]) + dp[j - 1][k1][10].first + i) / pw[j - 1]) % 10 == a[i] && pw[j - 1] <= ((k * pw[j - 1]) + dp[j - 1][k1][10].first + i))
                s1.insert(i);
              if ((int) s1.size() > (int) dp[j][k][k1].second.size()) {
                dp[j][k][k1].first = (k * pw[j - 1]) + dp[j - 1][k1][10].first;
                dp[j][k][k1].second = s1;
              }
              if ((int) dp[j][k][k1].second.size() > (int) dp[j][k][10].second.size()) {
                dp[j][k][10] = dp[j][k][k1];
              }
            }
          }
        }
      }
    }

    int i_j, i_k = -1;

    for (int j = 1; j < 18; j++) {
      for (int k = 0; k < 10; k++)
        if (!(j == 1 && k == 0) && (int) dp[j][k][10].second.size() == n) {
          i_j = j;
          i_k = k;
          break;
        }
      if (i_k != -1)
        break;
    }

    string ans = "";

    while (i_j) {
      ans += (i_k + '0');
      if (i_j == 1) {
        break;
      }
      for (int k = 0; k < 10; k++) {
        if (dp[i_j][i_k][10].first - (i_k * pw[i_j - 1]) == dp[i_j - 1][k][10].first) {
          i_j--;
          i_k = k;
          break;
        }
      }
    }

    for (int i = 0; i < (int) ans.size(); i++) {
      if (ans[i] != '0') {
        cout << ans.substr(i) << '\n';
        break;
      }
    }
  }
 
  return 0;
}

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