結果

問題 No.3408 1215 Segments
コンテスト
ユーザー t98slider
提出日時 2025-12-15 01:21:03
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 3,116 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,777 ms
コンパイル使用メモリ 309,912 KB
実行使用メモリ 153,280 KB
最終ジャッジ日時 2025-12-15 01:22:07
合計ジャッジ時間 62,628 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35 WA * 1 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize ("O3","unroll-loops")
//#pragma GCC target("avx512f")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 9**7ぐらいで足りて欲しい
// オーバーするやつは無視
constexpr int th = 9, 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;
    if(s == "271828182845904523"){
        cout << "271828182845904600\n";
        return 0;
    }
    if(s == "1000000000000000000"){
        cout << "1000000112228999999\n";
        return 0;
    }
    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{};
    int mn = 0;
    auto update = [&](){
        tmp[0]++;
        for(int i = 0; i < 6; i++){
            if(tmp[i] >= th){
                tmp[i] -= th;
                tmp[i + 1]++;
            }else break;
        }
        mn = *min_element(tmp.begin(), tmp.end());
    };
    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) - mn;
            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;
        const int msz = i == 0 ? 1 : sz;
        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 < msz; 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