509C - Sums of Digits - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define LSB(i) ((i) & (-i))
#define ll long long
const int dx[]{-1,1,0,0,-1,-1,1,1};
const int dy[]{0,0,1,-1,-1,1,-1,1};
const int MOD = 1e9+7;
const int inf = 1e9 + 1; 

#define int ll
#define x first
#define y second

string s;
int x;
string res;
int dp[335][301][2], vst[335][301][2], vs;

bool sol(int i, int sum, bool gt){  
    if(sum > x) return 0;
    if(i == s.size()) return sum == x;
    auto& ret = dp[i][sum][gt];
    if(vst[i][sum][gt] == vs) return ret;
    vst[i][sum][gt] = vs;
    ret = 0;
    for(int d = (gt ? 0 : s[i]); d <= 9; ++d){
        if(sol(i+1, sum+d, gt || d > s[i]))
            return ret = 1;
    }
    return ret;
}

string build(int i, int sum, bool gt, bool nonzero = 0){
    if(i == s.size()) return "";
    for(int d = (gt ? 0 : s[i]); d <= 9; ++d){
        if(sol(i+1, sum+d, gt || d > s[i])){
            return (nonzero || d ? to_string(d) : "" ) +
            build(i+1, sum+d, gt || d > s[i], nonzero || d);
        }
    }
    return "";
}



void plusOne(string& s){
    for(int i = s.size()-1; i >= 0; --i){
        int d = s[i]-'0';
        int r = (d+1)%10;
        if(r == 0) s[i] = '0';
        else {
            ++s[i];
            return;
        }
    }
    s =  string(1, '1') + s;
}

void solve(int testCase)  {
    s = string(335, '0');
    for(char& d:s) d-= '0';
    int n; cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> x;
        ++vs;
        sol(0,0,0);
        string res =  build(0,0,0);
        cout << res << '\n';
        plusOne(res);
        s = string(335-res.size(), '0') + res;
        for(char& d:s) d-= '0';
    }
}

int32_t main(){
    fastio();   
    int t = 1;
   // cin >> t;
    for(int i = 1; i <= t; ++i){
        solve(i);
    }
    return 0;
}