Submission #65294916

---

Source Code Expand

// https://atcoder.jp/contests/abc403/tasks/abc403_f
// 2025年04月27日 23時25分37秒
#include <bits/stdc++.h>
// #include <atcoder/all>
// using namespace atcoder;
// using mint = modint998244353;
// using mint = modint1000000007;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, n) for (long long int i = 0; i < (n); ++i)
#define rep2(i, k, n) for (long long int i = (k); i < (n); ++i)
using namespace std;
using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<ll>>;

const ll INF = (ll)2e18 + 9;
// const int INF = (int)2e9 + 7;

template <typename T>
void chmin(T& a, T b) {
    a = min(a, b);
}
template <typename T>
void chmax(T& a, T b) {
    a = max(a, b);
}

template <typename T>
void print(vector<T> v) {
    int n = v.size();
    rep(i, n) {
        if (i == 0)
            cout << v[i];
        else
            cout << ' ' << v[i];
    }
    cout << endl;
}

void yesno(bool x) {
    cout << (x ? "Yes" : "No") << '\n';
}

void solve();

int main() {
    solve();
    return 0;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    map<int, string> memo;
    map<int, char> memoc;
    auto dfs = [&](auto dfs, int n) -> string {
        if (n == 1)
            return "1";
        if (n == 11)
            return "11";
        if (n == 111)
            return "111";
        if (n == 1111)
            return "1111";
        if (memo.count(n))
            return memo[n];

        string ans = "";
        ll sz = INF;
        char c = '_';
        rep2(i, 2, n) {
            if (n % i == 0) {
                string l = dfs(dfs, i);
                string r = dfs(dfs, n / i);
                if (memoc[i] == '+') {
                    l = "(" + l + ")";
                }
                if (memoc[n / i] == '+') {
                    r = "(" + r + ")";
                }
                if ((ll)l.size() + (ll)r.size() + 1 < sz) {
                    ans = l + "*" + r;
                    memoc[n] = '*';
                    sz = ans.size();
                }
            }
        }
        rep2(i, 1, n) {
            string l = dfs(dfs, i);
            string r = dfs(dfs, n - i);
            ll tmpsz = (ll)l.size() + (ll)r.size() + 1;
            if (tmpsz < sz) {
                ans = l + "+" + r;
                sz = tmpsz;
                memoc[n] = '+';
            }
        }
        return memo[n] = ans;
    };

    cout << dfs(dfs, N) << endl;
}

Submission Info

Compile Error

Main.cpp: In instantiation of ‘solve()::<lambda(auto:53, int)> [with auto:53 = solve()::<lambda(auto:53, int)>; std::string = std::__cxx11::basic_string<char>]’:
Main.cpp:108:16:   required from here
Main.cpp:77:14: warning: unused variable ‘c’ [-Wunused-variable]
   77 |         char c = '_';
      |              ^

Judge Result