oj.uz

Submission #1037787

# Submission time Handle Problem Language Result Execution time Memory
1037787 2024-07-29T08:21:59 Z 정희우(#10983) Cookies (JOI23_cookies) C++17
0 / 100
 134 ms 519556 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});
    vector<intp> st;
    for(auto c : boxs)
    {
        cout << c << ' ';
        for(int i=0;i<c;i++)
        {
            intp p=pq.top();pq.pop();
            cout << p.second << ' ';
            st.push_back({p.first-1,p.second});
        }
        while(!st.empty())
        {
            pq.push(st.back());
            st.pop_back();
        }
        cout << '\n';
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 519540 KB Output is correct
2 Correct 105 ms 519556 KB Output is correct
3 Correct 134 ms 519364 KB Output is correct
4 Correct 105 ms 519468 KB Output is correct
5 Incorrect 97 ms 519504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 519388 KB Output is correct
2 Correct 90 ms 519508 KB Output is correct
3 Correct 89 ms 519512 KB Output is correct
4 Correct 104 ms 519508 KB Output is correct
5 Correct 94 ms 519508 KB Output is correct
6 Correct 89 ms 519504 KB Output is correct
7 Correct 94 ms 519536 KB Output is correct
8 Correct 98 ms 519504 KB Output is correct
9 Incorrect 96 ms 519408 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 519508 KB Output is correct
2 Correct 93 ms 519504 KB Output is correct
3 Correct 98 ms 519504 KB Output is correct
4 Correct 98 ms 519372 KB Output is correct
5 Correct 94 ms 519504 KB Output is correct
6 Incorrect 97 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 109 ms 519540 KB Output is correct
2 Correct 105 ms 519556 KB Output is correct
3 Correct 134 ms 519364 KB Output is correct
4 Correct 105 ms 519468 KB Output is correct
5 Incorrect 97 ms 519504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 519540 KB Output is correct
2 Correct 105 ms 519556 KB Output is correct
3 Correct 134 ms 519364 KB Output is correct
4 Correct 105 ms 519468 KB Output is correct
5 Incorrect 97 ms 519504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 519540 KB Output is correct
2 Correct 105 ms 519556 KB Output is correct
3 Correct 134 ms 519364 KB Output is correct
4 Correct 105 ms 519468 KB Output is correct
5 Incorrect 97 ms 519504 KB Output isn't correct
6 Halted 0 ms 0 KB -