oj.uz

Submission #234008

# Submission time Handle Problem Language Result Execution time Memory
234008 2020-05-22T18:51:39 Z Sorting Devil's Share (RMI19_devil) C++14
0 / 100
 1500 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;

int d[10], k;

string get_largest_string(const string &s){
    string answer = "";
    for(int i = 0; i < k; ++i)
        answer += s[i];

    for(int i = k; i < (int)s.size(); ++i){
        string curr = "";
        for(int j = i - k + 1; j <= i; ++j)
            curr += s[j];

        if(curr > answer)
            answer = curr;
    }

    return answer;
}

pair<string, string> recursion(int cnt, const string &s){
    if(!cnt)
        return {get_largest_string(s), s};

    pair<string, string> answer = {"", ""};
    for(int i = 1; i <= 9; ++i){
        if(d[i]){
            --d[i];
            pair<string, string> candidate = recursion(cnt - 1, s + (char)('0' + i));
            ++d[i];

            if(answer.first == "" || candidate < answer)
                answer = candidate;
        }
    }

    return answer;
}

void read(){
    cin >> k;
    
    for(int i = 1; i <= 9; ++i)
        cin >> d[i];
}

void solve_test(){
    read();

    int cnt = 0;
    for(int i = 1; i <= 9; ++i)
        cnt += d[i];

    cout << recursion(cnt, "").second << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--)
        solve_test();
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1585 ms 504 KB Time limit exceeded

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1586 ms 384 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 1591 ms 504 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 1585 ms 504 KB Time limit exceeded