結果

問題 No.3408 1215 Segments
コンテスト
ユーザー t98slider
提出日時 2025-12-15 00:44:26
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 2,923 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,503 ms
コンパイル使用メモリ 203,664 KB
実行使用メモリ 814,412 KB
最終ジャッジ日時 2025-12-15 00:44:32
合計ジャッジ時間 5,701 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1 -- * 3
other -- * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

long long intpow(long long a, long long b){ 
    long long ans = 1; 
    while(b){ 
        if(b & 1) ans *= a; 
        a *= a; 
        b >>= 1; 
    } 
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    vector<pair<int,int>> tb(10, make_pair(-1, -1));
    tb[0].first  = 0b1111110;
    tb[0].second = 0b0011101;
    tb[1].first  = 0b0000110;
    tb[1].second = 0b0110000;
    tb[2].first  = 0b1011011;
    tb[3].first  = 0b1001111;
    tb[4].first  = 0b0100111;
    tb[5].first  = 0b1101101;
    tb[6].first  = 0b1111101;
    tb[6].second = 0b0111101;
    tb[7].first  = 0b1000110;
    tb[7].second = 0b1100110;
    tb[8].first  = 0;
    tb[9].first  = 0b1101111;
    tb[9].second = 0b1100111;

    // 9**7ぐらいで足りて欲しい
    // オーバーするやつは無視
    constexpr int th = 10, sz = th * th * th * th * th * th * th;
    constexpr ll inf = 1ll << 62;
    s = "0" + s;
    int n = s.size();
    vector<array<array<ll, sz>,2>> dp(n + 1);
    for(int i = 0; i <= n; i++){
        dp[i][0].fill(inf);
        dp[i][1].fill(inf);
    }
    array<int, 7> tmp{};
    auto update = [&](){
        tmp[0]++;
        for(int i = 0; i < 6; i++){
            if(tmp[i] >= th){
                tmp[i] -= th;
                tmp[i + 1]++;
            }else break;
        }
    };
    auto f = [&](int S){
        if(S == -1) return -1;
        int res = 0, d = 1;
        for(int i = 0; i < 7; i++, d *= th){
            int v = tmp[i] + (S >> i & 1);
            if(v >= th) return -1;
            res += d * v;
        }
        return res;
    };
    dp[0][1][0] = 0;
    dp[1][1][0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 2; j++){
            int l = j ? s[i] - '0' : 0;
            if(i == 0) l = max(l, 1);
            tmp.fill(0);
            for(int k = 0; k < sz; k++, update()){
                if(dp[i][j][k] == inf) continue;
                for(int v = l; v <= 9; v++){
                    auto [v0, v1] = tb[v];
                    v0 = f(v0);
                    if(v0 != -1){
                        auto &&nv = dp[i + 1][j & (v == l)][v0];
                        nv = min(nv, dp[i][j][k] * 10 + v);
                    }
                    if(v1 == -1) continue;
                    v1 = f(v1);
                    if(v1 != -1){
                        auto &&nv = dp[i + 1][j & (v == l)][v1];
                        nv = min(nv, dp[i][j][k] * 10 + v);
                    }
                }
            }
        }
    }
    ll ans = inf;
    for(int j = 0; j < 2; j++){
        for(int k = 0; k < th; k++){
            int S = 0, d = 1;
            for(int l = 0; l < 7; l++){
                S += k * d;
                d *= th;
            }
            ans = min(ans, dp[n][j][S]);
        }
    }
    cout << ans << '\n';
}
0