結果

問題 No.3408 1215 Segments
コンテスト
ユーザー t98slider
提出日時 2025-12-15 00:49:47
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,728 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,927 ms
コンパイル使用メモリ 201,540 KB
実行使用メモリ 316,312 KB
最終ジャッジ日時 2025-12-15 00:51:08
合計ジャッジ時間 77,432 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 TLE * 1
other AC * 33 WA * 2 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

// 9**7ぐらいで足りて欲しい
// オーバーするやつは無視
constexpr int th = 10, sz = th * th * th * th * th * th * th;
constexpr ll inf = 1ll << 62;
array<array<ll, sz>,2> dp, ndp;
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;

    s = "0" + s;
    int n = s.size();
    for(int i = 0; i < 2; i++) dp[i].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[1][0] = 0;
    for(int i = 0; i < n; i++){
        ndp[0].fill(inf);
        ndp[1].fill(inf);
        if(i == 0) ndp[1][0] = 0;
        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[j][k] == inf) continue;
                for(int v = l; v <= 9; v++){
                    auto [v0, v1] = tb[v];
                    v0 = f(v0);
                    if(v0 != -1){
                        auto &&nv = ndp[j & (v == l)][v0];
                        nv = min(nv, dp[j][k] * 10 + v);
                    }
                    if(v1 == -1) continue;
                    v1 = f(v1);
                    if(v1 != -1){
                        auto &&nv = ndp[j & (v == l)][v1];
                        nv = min(nv, dp[j][k] * 10 + v);
                    }
                }
            }
        }
        dp = ndp;
    }
    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[j][S]);
        }
    }
    cout << ans << '\n';
}
0