Contest Duration: - (local time) (120 minutes) Back to Home

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 2017-04-23 23:46:38+0900 D - 壊れた電卓 hamayanhamayan C++14 (GCC 5.4.1) 100 1394 Byte AC 4 ms 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