oj.uz

Submission #1037779

# Submission time Handle Problem Language Result Execution time Memory
1037779 2024-07-29T08:15:52 Z 정희우(#10983) Cookies (JOI23_cookies) C++17
0 / 100
 132 ms 519764 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;

const int MAX_N=510;

int n,m;
int arr[MAX_N],sarr[MAX_N],sum[MAX_N];
int box[MAX_N];
int dt[MAX_N][MAX_N][MAX_N];
priority_queue<intp> pq;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> arr[i];
        sarr[i]=arr[i];
    }
    sort(sarr,sarr+n,greater<int>());
    for(int i=0;i<n;i++)
        sum[i]=sarr[i]+((i) ? sum[i-1] : 0);
    cin >> m;
    for(int i=1;i<=m;i++)
        cin >> box[i];
    fill(dt[0][0],dt[0][0]+MAX_N*MAX_N*MAX_N,MAX_N);
    for(int i=sarr[0];i<=sum[n-1];i++)dt[0][i][0]=i;
    for(int b=1;b<=m;b++)
        for(int h=sum[n-1];h>=0;h--)
            for(int s=sum[box[b]];s<=sum[n-1];s++)
            {
                dt[b][h][s]=dt[b][h+1][s];
                if(s-h*(box[b]-box[b-1])>=0)
                    dt[b][h][s]=min(dt[b][h][s],dt[b-1][h][s-h*(box[b]-box[b-1])]);
            }
    if(dt[m][0][sum[n-1]]==MAX_N)
    {
        cout << -1;
        return 0;
    }
    cout << dt[m][0][sum[n-1]] << '\n';
    vint boxs;
    for(int b=m,h=0,s=sum[n-1];b+s>0;)
    {
        if(dt[b][h][s]==dt[b][h+1][s])
        {
            boxs.push_back(box[b]);
            h++;
        }
        else
        {
            s-=h*(box[b]-box[b-1]);
            b--;
        }
    }
    for(int i=0;i<n;i++)
        pq.push({arr[i],i+1});
    for(auto c : boxs)
    {
        cout << c << ' ';
        for(int i=0;i<c;i++)
        {
            intp p=pq.top();pq.pop();
            cout << p.second << ' ';
            pq.push({p.first-1,p.second});
        }
        cout << '\n';
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 519572 KB Output is correct
2 Correct 110 ms 519416 KB Output is correct
3 Correct 128 ms 519376 KB Output is correct
4 Correct 107 ms 519492 KB Output is correct
5 Incorrect 123 ms 519388 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 519504 KB Output is correct
2 Correct 105 ms 519508 KB Output is correct
3 Correct 99 ms 519512 KB Output is correct
4 Correct 105 ms 519388 KB Output is correct
5 Correct 101 ms 519764 KB Output is correct
6 Correct 124 ms 519560 KB Output is correct
7 Correct 104 ms 519580 KB Output is correct
8 Correct 104 ms 519552 KB Output is correct
9 Incorrect 132 ms 519508 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 519508 KB Output is correct
2 Correct 121 ms 519416 KB Output is correct
3 Correct 102 ms 519532 KB Output is correct
4 Correct 106 ms 519428 KB Output is correct
5 Correct 123 ms 519608 KB Output is correct
6 Incorrect 119 ms 519508 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 519572 KB Output is correct
2 Correct 110 ms 519416 KB Output is correct
3 Correct 128 ms 519376 KB Output is correct
4 Correct 107 ms 519492 KB Output is correct
5 Incorrect 123 ms 519388 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 519572 KB Output is correct
2 Correct 110 ms 519416 KB Output is correct
3 Correct 128 ms 519376 KB Output is correct
4 Correct 107 ms 519492 KB Output is correct
5 Incorrect 123 ms 519388 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 519572 KB Output is correct
2 Correct 110 ms 519416 KB Output is correct
3 Correct 128 ms 519376 KB Output is correct
4 Correct 107 ms 519492 KB Output is correct
5 Incorrect 123 ms 519388 KB Output isn't correct
6 Halted 0 ms 0 KB -