oj.uz

Submission #493968

# Submission time Handle Problem Language Result Execution time Memory
493968 2021-12-13T14:00:44 Z leaked Devil's Share (RMI19_devil) C++14
0 / 100
 1500 ms 460 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
vec<int>cnt(5,0);
string cr;
string prec[4][4][4][4][16];
string answer[4][4][4][4][16];
string find_max(string ans,int k){
    string me=ans.substr(0,k);
    for(int i=0;i+k-1<sz(ans);i++){
        string w=ans.substr(i,k);
        me=max(me,w);
    }
    return me;
}
void rec(int i,int mx){
    if(i){
        for(int k=1;k<=i;k++){
            string me=find_max(cr,k);
            if(prec[cnt[0]][cnt[1]][cnt[2]][cnt[3]][k]=="" ||
               prec[cnt[0]][cnt[1]][cnt[2]][cnt[3]][k]>me){
                prec[cnt[0]][cnt[1]][cnt[2]][cnt[3]][k]=me;
                answer[cnt[0]][cnt[1]][cnt[2]][cnt[3]][k]=cr;
               }
        }
    }
    for(int j=0;j<=3;j++){
        ++cnt[j];
        if(cnt[j]<=3){
            cr.pb('1'+j);
            rec(i+1,max(j,mx));
            cr.pop_back();
        }
        --cnt[j];
    }
}

signed main(){
    fast_rmi;
    rec(0,-1);
//    for(int i=0;i<4;i++){
//        for(int j=0;j<4;j++){
//            for(int k=0;k<=3;k++){
//                for(int t=0;t<=3;t++){
//                    for(int cnt=1;cnt<=i+j+k+t;cnt++){
//                        cout<<"answer["<<i<<"]["<<j<<"]["<<k<<"]["<<t<<"]["<<cnt<<"]="<<"\""<<answer[i][j][k][t][cnt]<<"\""<<";"<<'\n';
//                    }
//                }
//            }
//        }
//    }
//    return 0;
    int t;
    cin>>t;
    while(t--){
        vec<int> cnt(10,0);
        int ok=1,sum=0;
        int k;
        cin>>k;
        for(int i=1;i<10;i++)
            cin>>cnt[i-1],ok&=(i>=4?cnt[i-1]==0:1),sum+=cnt[i-1];
        if(!ok){
            assert(false);
            continue;
        }
        string ans=answer[cnt[0]][cnt[1]][cnt[2]][cnt[3]][k];
//        assert(sz(to_string(ans))==sum);
        cout<<ans<<'\n';
    }
    return 0;
}
/*
1
6
3 3 3 3 0 0 0 0 0 0
*/

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1569 ms 460 KB Time limit exceeded

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1574 ms 460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1578 ms 460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1569 ms 460 KB Time limit exceeded