oj.uz

Submission #789326

# Submission time Handle Problem Language Result Execution time Memory
789326 2023-07-21T09:16:37 Z 이동현(#10044) Cookies (JOI23_cookies) C++17
7 / 100
 443 ms 28692 KB 
#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

const int NS = 15004;
const int SZ = 15004;
int n, m;
int a[NS], b[NS];
int mn[NS];
bitset<15004> dp[2][SZ];
pair<int, int> srt[NS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    int asum = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        srt[i] = {a[i], i};
        asum += a[i];
    }
    cin >> m;
    for(int i = 1; i <= m; ++i){
        cin >> b[i];
    }

    sort(b + 1, b + m + 1);
    reverse(b + 1, b + m + 1);

    for(int i = 1; i <= SZ - 4; ++i){
        for(int j = 1; j <= n; ++j){
            mn[i] += min(i, a[j]);
        }
        mn[i] = min(mn[i], SZ - 4);
    }

    dp[0][0][0] = 1;
    for(int i = 1; i <= m; ++i){
        for(int j = 0; j <= SZ - 4; ++j){
            for(int k = 0; k <= mn[j]; ++k){
                if(dp[i - 1][j][k]){
                    dp[i][j][k] = 1;
                }
                if(j && k >= b[i] && dp[i][j - 1][k - b[i]]){
                    dp[i][j][k] = 1;
                }
            }
        }
    }

    int ans = -1;
    for(int i = 1; i <= SZ - 4; ++i){
        if(dp[m][i][asum]){
            ans = i;
            break;
        }
    }

    cout << ans << '\n';
    if(ans == -1){
        return 0;
    }
    vector<int> lst;
    auto makelst = [&](auto&&self, int i, int j, int k)->void{
        if(!i) return;
        if(dp[i - 1][j][k]){
            self(self, i - 1, j, k);
        }
        else{
            self(self, i, j - 1, k - b[i]);
            lst.push_back(b[i]);
        }
    };
    makelst(makelst, m, ans, asum);

    for(auto&i:lst){
        cout << i << ' ';
        sort(srt + 1, srt + n + 1);
        reverse(srt + 1, srt + n + 1);
        while(!srt[n].first){
            --n;
        }

        for(int j = 1; j <= i; ++j){
            assert(srt[j].first >= 1);
            --srt[j].first;
            cout << srt[j].second << ' ';
        }
        cout << '\n';
    }

    assert(srt[0].first == 0);
    
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 800 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 31 ms 1484 KB Output is correct
6 Correct 18 ms 544 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 22 ms 1484 KB Output is correct
9 Correct 95 ms 6136 KB Output is correct
10 Correct 188 ms 28692 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 6 ms 468 KB Output is correct
15 Correct 6 ms 468 KB Output is correct
16 Correct 21 ms 636 KB Output is correct
17 Correct 19 ms 628 KB Output is correct
18 Correct 344 ms 7556 KB Output is correct
19 Correct 443 ms 9948 KB Output is correct
20 Correct 372 ms 980 KB Output is correct
21 Correct 418 ms 632 KB Output is correct
22 Correct 354 ms 836 KB Output is correct
23 Correct 31 ms 468 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 800 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 800 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 800 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -