Submission #1240951


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




typedef long long ll;
#define INF 1e18
ll A; int K;
//-----------------------------------------------------------------------------------
ll dp[20][1 << 10][2];
ll solve() {
    rep(i, 0, 20) rep(j, 0, 1 << 10) {
        dp[i][j][0] = -INF;
        dp[i][j][1] = INF;
    }

    string s = to_string(A);
    int n = s.length();

    dp[0][0][0] = 0;
    ll x = 0;
    rep(i, 0, n) {
        x = x * 10 + s[i] - '0';
        rep(ma, 0, 1 << 10) rep(f, 0, 2) {
            int cnt = 0;
            rep(j, 0, 10) if (ma & (1 << j)) cnt++;

            rep(j, 0, 10) {
                ll ne = dp[i][ma][f] * 10 + j;

                if (cnt == K && (ma & (1 << j)) == 0) continue;

                if (ne < x) {
                    dp[i + 1][ma | (1 << j)][0] = max(dp[i + 1][ma | (1 << j)][0], ne);
                }
                else {
                    dp[i + 1][ma | (1 << j)][1] = min(dp[i + 1][ma | (1 << j)][1], ne);
                }
            }
        }
    }

    ll ans = INF;
    rep(i, 0, n + 1) rep(ma, 0, 1 << 10) rep(f, 0, 2) ans = min(ans, abs(A - dp[i][ma][f]));
    return ans;
}
//-----------------------------------------------------------------------------------
int main() {
    cin >> A >> K;

    cout << solve() << endl;
}

Submission Info

Submission Time
Task D - 壊れた電卓
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1394 Byte
Status AC
Exec Time 4 ms
Memory 512 KB

Judge Result

Set Name sub All
Score / Max Score 30 / 30 70 / 70
Status
AC × 32
AC × 57
Set Name Test Cases
sub test_01A.txt, test_02A.txt, test_04A.txt, test_05A.txt, test_07A.txt, test_09A.txt, test_10A.txt, test_11A.txt, test_12A.txt, test_13A.txt, test_15A.txt, test_17A.txt, test_18A.txt, test_19A.txt, test_21A.txt, test_22A.txt, test_23A.txt, test_25A.txt, test_27A.txt, test_28A.txt, test_29A.txt, test_31A.txt, test_33A.txt, test_34A.txt, test_35A.txt, test_37A.txt, test_38A.txt, test_40A.txt, test_42A.txt, test_44A.txt, test_46A.txt, test_48A.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, test_01A.txt, test_02A.txt, test_03.txt, test_04A.txt, test_05A.txt, test_06.txt, test_07A.txt, test_08.txt, test_09A.txt, test_10A.txt, test_11A.txt, test_12A.txt, test_13A.txt, test_14.txt, test_15A.txt, test_16.txt, test_17A.txt, test_18A.txt, test_19A.txt, test_20.txt, test_21A.txt, test_22A.txt, test_23A.txt, test_24.txt, test_25A.txt, test_26.txt, test_27A.txt, test_28A.txt, test_29A.txt, test_30.txt, test_31A.txt, test_32.txt, test_33A.txt, test_34A.txt, test_35A.txt, test_36.txt, test_37A.txt, test_38A.txt, test_39.txt, test_40A.txt, test_41.txt, test_42A.txt, test_43.txt, test_44A.txt, test_45.txt, test_46A.txt, test_47.txt, test_48A.txt, test_49.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 512 KB
sample_02.txt AC 2 ms 512 KB
sample_03.txt AC 2 ms 512 KB
sample_04.txt AC 2 ms 512 KB
test_01A.txt AC 1 ms 512 KB
test_02A.txt AC 2 ms 512 KB
test_03.txt AC 2 ms 512 KB
test_04A.txt AC 1 ms 512 KB
test_05A.txt AC 2 ms 512 KB
test_06.txt AC 3 ms 512 KB
test_07A.txt AC 2 ms 512 KB
test_08.txt AC 2 ms 512 KB
test_09A.txt AC 1 ms 512 KB
test_10A.txt AC 2 ms 512 KB
test_11A.txt AC 2 ms 512 KB
test_12A.txt AC 1 ms 512 KB
test_13A.txt AC 2 ms 512 KB
test_14.txt AC 2 ms 512 KB
test_15A.txt AC 1 ms 512 KB
test_16.txt AC 2 ms 512 KB
test_17A.txt AC 2 ms 512 KB
test_18A.txt AC 2 ms 512 KB
test_19A.txt AC 2 ms 512 KB
test_20.txt AC 2 ms 512 KB
test_21A.txt AC 2 ms 512 KB
test_22A.txt AC 2 ms 512 KB
test_23A.txt AC 2 ms 512 KB
test_24.txt AC 4 ms 512 KB
test_25A.txt AC 2 ms 512 KB
test_26.txt AC 3 ms 512 KB
test_27A.txt AC 2 ms 512 KB
test_28A.txt AC 2 ms 512 KB
test_29A.txt AC 1 ms 512 KB
test_30.txt AC 2 ms 512 KB
test_31A.txt AC 2 ms 512 KB
test_32.txt AC 2 ms 512 KB
test_33A.txt AC 1 ms 512 KB
test_34A.txt AC 2 ms 512 KB
test_35A.txt AC 2 ms 512 KB
test_36.txt AC 2 ms 512 KB
test_37A.txt AC 1 ms 512 KB
test_38A.txt AC 2 ms 512 KB
test_39.txt AC 3 ms 512 KB
test_40A.txt AC 2 ms 512 KB
test_41.txt AC 2 ms 512 KB
test_42A.txt AC 2 ms 512 KB
test_43.txt AC 2 ms 512 KB
test_44A.txt AC 2 ms 512 KB
test_45.txt AC 2 ms 512 KB
test_46A.txt AC 2 ms 512 KB
test_47.txt AC 2 ms 512 KB
test_48A.txt AC 2 ms 512 KB
test_49.txt AC 2 ms 512 KB