Submission #1037796

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1037796	2024-07-29T08:30:08 Z	정희우(#10983)	Cookies (JOI23_cookies)	C++17	6 / 100	187 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]-1];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
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	519408 KB	Output is correct
2	Correct	131 ms	519516 KB	Output is correct
3	Correct	118 ms	519396 KB	Output is correct
4	Correct	109 ms	519508 KB	Output is correct
5	Correct	108 ms	519496 KB	Output is correct
6	Correct	109 ms	519764 KB	Output is correct
7	Correct	110 ms	519508 KB	Output is correct
8	Correct	109 ms	519504 KB	Output is correct
9	Correct	109 ms	519504 KB	Output is correct
10	Correct	187 ms	519420 KB	Output is correct
11	Correct	132 ms	519508 KB	Output is correct
12	Correct	113 ms	519616 KB	Output is correct
13	Correct	156 ms	519624 KB	Output is correct
14	Correct	136 ms	519508 KB	Output is correct
15	Correct	140 ms	519388 KB	Output is correct
16	Correct	156 ms	519504 KB	Output is correct
17	Correct	108 ms	519764 KB	Output is correct
18	Correct	109 ms	519460 KB	Output is correct
19	Correct	109 ms	519416 KB	Output is correct
20	Correct	113 ms	519508 KB	Output is correct
21	Correct	121 ms	519508 KB	Output is correct
22	Correct	146 ms	519504 KB	Output is correct
23	Correct	144 ms	519504 KB	Output is correct
24	Correct	106 ms	519504 KB	Output is correct
25	Correct	112 ms	519512 KB	Output is correct
26	Correct	111 ms	519508 KB	Output is correct
27	Correct	117 ms	519492 KB	Output is correct
28	Correct	113 ms	519508 KB	Output is correct

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	519508 KB	Output is correct
2	Correct	112 ms	519532 KB	Output is correct
3	Correct	105 ms	519508 KB	Output is correct
4	Correct	129 ms	519504 KB	Output is correct
5	Correct	104 ms	519500 KB	Output is correct
6	Correct	99 ms	519508 KB	Output is correct
7	Correct	108 ms	519556 KB	Output is correct
8	Correct	108 ms	519504 KB	Output is correct
9	Incorrect	105 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	100 ms	519508 KB	Output is correct
2	Correct	99 ms	519500 KB	Output is correct
3	Correct	108 ms	519500 KB	Output is correct
4	Correct	105 ms	519504 KB	Output is correct
5	Correct	103 ms	519504 KB	Output is correct
6	Correct	104 ms	519504 KB	Output is correct
7	Correct	105 ms	519488 KB	Output is correct
8	Correct	107 ms	519508 KB	Output is correct
9	Correct	105 ms	519504 KB	Output is correct
10	Correct	102 ms	519520 KB	Output is correct
11	Correct	105 ms	519524 KB	Output is correct
12	Correct	100 ms	519392 KB	Output is correct
13	Correct	101 ms	519508 KB	Output is correct
14	Correct	94 ms	519504 KB	Output is correct
15	Correct	98 ms	519576 KB	Output is correct
16	Correct	100 ms	519556 KB	Output is correct
17	Correct	101 ms	519504 KB	Output is correct
18	Correct	99 ms	519504 KB	Output is correct
19	Correct	99 ms	519420 KB	Output is correct
20	Correct	99 ms	519504 KB	Output is correct
21	Correct	107 ms	519516 KB	Output is correct
22	Correct	103 ms	519504 KB	Output is correct
23	Incorrect	119 ms	519504 KB	Number of cookies does not match with A_i
24	Halted	0 ms	0 KB	-

Subtask #4
0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	519408 KB	Output is correct
2	Correct	131 ms	519516 KB	Output is correct
3	Correct	118 ms	519396 KB	Output is correct
4	Correct	109 ms	519508 KB	Output is correct
5	Correct	108 ms	519496 KB	Output is correct
6	Correct	109 ms	519764 KB	Output is correct
7	Correct	110 ms	519508 KB	Output is correct
8	Correct	109 ms	519504 KB	Output is correct
9	Correct	109 ms	519504 KB	Output is correct
10	Correct	187 ms	519420 KB	Output is correct
11	Correct	132 ms	519508 KB	Output is correct
12	Correct	113 ms	519616 KB	Output is correct
13	Correct	156 ms	519624 KB	Output is correct
14	Correct	136 ms	519508 KB	Output is correct
15	Correct	140 ms	519388 KB	Output is correct
16	Correct	156 ms	519504 KB	Output is correct
17	Correct	108 ms	519764 KB	Output is correct
18	Correct	109 ms	519460 KB	Output is correct
19	Correct	109 ms	519416 KB	Output is correct
20	Correct	113 ms	519508 KB	Output is correct
21	Correct	121 ms	519508 KB	Output is correct
22	Correct	146 ms	519504 KB	Output is correct
23	Correct	144 ms	519504 KB	Output is correct
24	Correct	106 ms	519504 KB	Output is correct
25	Correct	112 ms	519512 KB	Output is correct
26	Correct	111 ms	519508 KB	Output is correct
27	Correct	117 ms	519492 KB	Output is correct
28	Correct	113 ms	519508 KB	Output is correct
29	Correct	100 ms	519508 KB	Output is correct
30	Correct	99 ms	519500 KB	Output is correct
31	Correct	108 ms	519500 KB	Output is correct
32	Correct	105 ms	519504 KB	Output is correct
33	Correct	103 ms	519504 KB	Output is correct
34	Correct	104 ms	519504 KB	Output is correct
35	Correct	105 ms	519488 KB	Output is correct
36	Correct	107 ms	519508 KB	Output is correct
37	Correct	105 ms	519504 KB	Output is correct
38	Correct	102 ms	519520 KB	Output is correct
39	Correct	105 ms	519524 KB	Output is correct
40	Correct	100 ms	519392 KB	Output is correct
41	Correct	101 ms	519508 KB	Output is correct
42	Correct	94 ms	519504 KB	Output is correct
43	Correct	98 ms	519576 KB	Output is correct
44	Correct	100 ms	519556 KB	Output is correct
45	Correct	101 ms	519504 KB	Output is correct
46	Correct	99 ms	519504 KB	Output is correct
47	Correct	99 ms	519420 KB	Output is correct
48	Correct	99 ms	519504 KB	Output is correct
49	Correct	107 ms	519516 KB	Output is correct
50	Correct	103 ms	519504 KB	Output is correct
51	Incorrect	119 ms	519504 KB	Number of cookies does not match with A_i
52	Halted	0 ms	0 KB	-

Subtask #5
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	519408 KB	Output is correct
2	Correct	131 ms	519516 KB	Output is correct
3	Correct	118 ms	519396 KB	Output is correct
4	Correct	109 ms	519508 KB	Output is correct
5	Correct	108 ms	519496 KB	Output is correct
6	Correct	109 ms	519764 KB	Output is correct
7	Correct	110 ms	519508 KB	Output is correct
8	Correct	109 ms	519504 KB	Output is correct
9	Correct	109 ms	519504 KB	Output is correct
10	Correct	187 ms	519420 KB	Output is correct
11	Correct	132 ms	519508 KB	Output is correct
12	Correct	113 ms	519616 KB	Output is correct
13	Correct	156 ms	519624 KB	Output is correct
14	Correct	136 ms	519508 KB	Output is correct
15	Correct	140 ms	519388 KB	Output is correct
16	Correct	156 ms	519504 KB	Output is correct
17	Correct	108 ms	519764 KB	Output is correct
18	Correct	109 ms	519460 KB	Output is correct
19	Correct	109 ms	519416 KB	Output is correct
20	Correct	113 ms	519508 KB	Output is correct
21	Correct	121 ms	519508 KB	Output is correct
22	Correct	146 ms	519504 KB	Output is correct
23	Correct	144 ms	519504 KB	Output is correct
24	Correct	106 ms	519504 KB	Output is correct
25	Correct	112 ms	519512 KB	Output is correct
26	Correct	111 ms	519508 KB	Output is correct
27	Correct	117 ms	519492 KB	Output is correct
28	Correct	113 ms	519508 KB	Output is correct
29	Correct	100 ms	519508 KB	Output is correct
30	Correct	99 ms	519500 KB	Output is correct
31	Correct	108 ms	519500 KB	Output is correct
32	Correct	105 ms	519504 KB	Output is correct
33	Correct	103 ms	519504 KB	Output is correct
34	Correct	104 ms	519504 KB	Output is correct
35	Correct	105 ms	519488 KB	Output is correct
36	Correct	107 ms	519508 KB	Output is correct
37	Correct	105 ms	519504 KB	Output is correct
38	Correct	102 ms	519520 KB	Output is correct
39	Correct	105 ms	519524 KB	Output is correct
40	Correct	100 ms	519392 KB	Output is correct
41	Correct	101 ms	519508 KB	Output is correct
42	Correct	94 ms	519504 KB	Output is correct
43	Correct	98 ms	519576 KB	Output is correct
44	Correct	100 ms	519556 KB	Output is correct
45	Correct	101 ms	519504 KB	Output is correct
46	Correct	99 ms	519504 KB	Output is correct
47	Correct	99 ms	519420 KB	Output is correct
48	Correct	99 ms	519504 KB	Output is correct
49	Correct	107 ms	519516 KB	Output is correct
50	Correct	103 ms	519504 KB	Output is correct
51	Incorrect	119 ms	519504 KB	Number of cookies does not match with A_i
52	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	519408 KB	Output is correct
2	Correct	131 ms	519516 KB	Output is correct
3	Correct	118 ms	519396 KB	Output is correct
4	Correct	109 ms	519508 KB	Output is correct
5	Correct	108 ms	519496 KB	Output is correct
6	Correct	109 ms	519764 KB	Output is correct
7	Correct	110 ms	519508 KB	Output is correct
8	Correct	109 ms	519504 KB	Output is correct
9	Correct	109 ms	519504 KB	Output is correct
10	Correct	187 ms	519420 KB	Output is correct
11	Correct	132 ms	519508 KB	Output is correct
12	Correct	113 ms	519616 KB	Output is correct
13	Correct	156 ms	519624 KB	Output is correct
14	Correct	136 ms	519508 KB	Output is correct
15	Correct	140 ms	519388 KB	Output is correct
16	Correct	156 ms	519504 KB	Output is correct
17	Correct	108 ms	519764 KB	Output is correct
18	Correct	109 ms	519460 KB	Output is correct
19	Correct	109 ms	519416 KB	Output is correct
20	Correct	113 ms	519508 KB	Output is correct
21	Correct	121 ms	519508 KB	Output is correct
22	Correct	146 ms	519504 KB	Output is correct
23	Correct	144 ms	519504 KB	Output is correct
24	Correct	106 ms	519504 KB	Output is correct
25	Correct	112 ms	519512 KB	Output is correct
26	Correct	111 ms	519508 KB	Output is correct
27	Correct	117 ms	519492 KB	Output is correct
28	Correct	113 ms	519508 KB	Output is correct
29	Correct	98 ms	519508 KB	Output is correct
30	Correct	112 ms	519532 KB	Output is correct
31	Correct	105 ms	519508 KB	Output is correct
32	Correct	129 ms	519504 KB	Output is correct
33	Correct	104 ms	519500 KB	Output is correct
34	Correct	99 ms	519508 KB	Output is correct
35	Correct	108 ms	519556 KB	Output is correct
36	Correct	108 ms	519504 KB	Output is correct
37	Incorrect	105 ms	519508 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Submission #1037796

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 0 / 7.0

Subtask #3 0 / 12.0

Subtask #4 0 / 45.0

Subtask #5 0 / 15.0

Subtask #6 0 / 15.0

Subtask #1
6.0 / 6.0

Subtask #2
0 / 7.0

Subtask #3
0 / 12.0

Subtask #4
0 / 45.0

Subtask #5
0 / 15.0

Subtask #6
0 / 15.0