Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- string s = to_string(r);
- int n = s.size();
- for (int i = 0; i <= n; i++)
- for (int j = 0; j < 10; j++)
- for (int k = 0; k < 10; k++)
- for (int l = 0; l < 2; l++) dp[i][j][k][l] = -1;
- dp[0][0][9][1] = 0;
- for (int i = 1; i <= n; i++){
- int dg = s[i-1] - '0';
- for (int j = 0; j <= dg; j++){
- for (int mx = 0; mx <= 9; mx++){
- for (int mn = 0; mn <= 9; mn++){
- if (dp[i-1][mx][mn][1] == -1) continue;
- dp[i][max(mx, j)][min(mn, j)][dg == j] = max(dp[i-1][mx][mn][1] * 10 + j, dp[i][max(mx, j)][min(mn, j)][dg == j]);
- }
- }
- }
- for (int j = 0; j <= 9; j++){
- for (int mx = 0; mx <= 9; mx++){
- for (int mn = 0; mn <= 9; mn++){
- if (dp[i-1][mx][mn][0] == -1) continue;
- dp[i][max(mx, j)][min(mn, j)][0] = max(dp[i-1][mx][mn][0] * 10 + j, dp[i][max(mx, j)][min(mn, j)][0]);
- }
- }
- }
- }
- vector <pair <int, int64> > v;
- for (int i = 0; i < 10; i++){
- for (int j = 0; j <= i; j++){
- for (int t = 0; t < 2; t++){
- if (dp[n][i][j][t] != -1) {
- v.push_back({i-j, dp[n][i][j][t]});
- }
- }
- }
- }
- sort(v.begin(), v.end());
- for (auto i: v) {
- if (i.second >= l) {
- cout << i.second << "\n";
- return;
- }
- }
Add Comment
Please, Sign In to add comment