답안 #804602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
804602	2023-08-03T10:09:34 Z	mousebeaver	Cookies (JOI23_cookies)	C++14	25 / 100	1000 ms	1620 KB

#define ll long long
#define INF numeric_limits<ll>::max()/2
#define pll pair<ll, ll>
#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<ll>>& output, ll cookies, vector<ll>& current, vector<ll>& a, vector<ll>& b)
{
    if(cookies > 0)
    {
        ll start = 0;
        if(current.size())
            start = current.back();
        for(ll j = start; j < (int) b.size() && b[j] <= cookies; j++)
        {
            current.push_back(j);
            dfs(output, cookies-b[j], current, a, b);
            current.pop_back();
        }
    }
    else
    {
        //Test the given state!!!
        if(output.size() && current.size() > output.size()) //No improvement possible
        {
            return;
        }

        vector<vector<ll>> res(current.size(), vector<ll> (0)); //pre-output
        priority_queue<pll, vector<pll>, less<pll>> q; //Free, index
        for(ll i = 0; i < (int) current.size(); i++)
        {
            q.push({b[current[i]], i});
        }

        for(ll i = 0; i < (int) a.size(); i++)
        {
            if(a[i] > (int) current.size())
            {
                return;
            }

            vector<pll> used(0); //Free, index
            for(ll j = 0; j < a[i]; j++)
            {
                ll c, index;
                tie(c, index) = q.top();
                if(c == 0)
                {
                    return;
                }
                q.pop();
                used.push_back({c-1, index});
                res[index].push_back(i+1);
            }
            for(pll p : used)
            {
                q.push(p);
            }            
        }

        output = res;
    }
}

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

    /*//Testing something!!!
    vector<ll> dp(16, 1);
    for(ll i = 2; i <= 15; i++)
    {
        for(ll j = 0; j+i <= 15; j++)
        {
            dp[j+i] += dp[j];
        }
    }
    cout<<"TEST: "<<dp[15]<<endl;
    return 0;*/

    bool sub1 = true;

    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll i = 0; i < n; i++)
    {
        cin>>a[i];
        if(a[i] != 1 || n > 500)
        {
            sub1 = false;
        }
    }
    ll m;
    cin>>m;
    vector<ll> b(m);
    for(ll i = 0; i < m; i++)
    {
        cin>>b[i];
    }

    if(sub1)
    {
        //Subtask 1:
        vector<pll> dp(n+1, {INF, -1}); //Number, last
        dp[0] = {0, 0};
        for(ll i = 0; i < n; i++)
        {
            for(ll j = 0; j < m && i+b[j] <= n; j++)
            {
                if(dp[i].first+1 < dp[i+b[j]].first)
                {
                    dp[i+b[j]].first = dp[i].first+1;
                    dp[i+b[j]].second = j;
                }
            }
        }

        if(dp[n].first == INF)
        {
            cout<<-1<<"\n";
        }
        else
        {
            cout<<dp[n].first<<"\n";
            ll k = n;
            ll counter = 1;
            while(k > 0)
            {
                ll box = b[dp[k].second];
                k -= box;
                cout<<box<<" ";
                while(box > 0)
                {
                    cout<<counter<<" ";
                    counter++;
                    box--;
                }
                cout<<"\n";
            }
        }
        return 0;
    }

    if(m == 1)
    {
        //Subtask 2:
        ll sum = 0;
        for(ll i : a)
        {
            sum += i;
        }
        
        if(sum%b[0] != 0 || *max_element(a.begin(), a.end()) > sum/b[0])
        {
            cout<<-1<<"\n";
        }
        else
        {
            vector<vector<ll>> output(sum/b[0], vector<ll> (0));
            priority_queue<pll, vector<pll>, greater<pll>> q; //Contained, index
            for(ll i = 0; i < sum/b[0]; i++)
            {
                q.push({0, i});
            }

            for(ll i = 0; i < n; i++)
            {
                vector<pll> used(0); //Contained, index
                for(ll j = 0; j < a[i]; j++)
                {
                    ll c, index;
                    tie(c, index) = q.top();
                    q.pop();
                    used.push_back({c+1, index});
                    output[index].push_back(i+1);
                }
                for(pll p : used)
                {
                    q.push(p);
                }
            }

            cout<<sum/b[0]<<"\n";
            for(ll i = 0; i < sum/b[0]; i++)
            {
                cout<<b[0]<<" ";
                for(ll j : output[i])
                {
                    cout<<j<<" ";
                }
                cout<<"\n";
            }
        }
        return 0;
    }

    //Subtask 3:
    vector<ll> current(0);
    vector<vector<ll>> output(0);
    ll sum = 0;
    for(ll i : a)
    {
        sum += i;
    }
    dfs(output, sum, current, a, b);
    
    if(output.empty())
    {
        cout<<-1<<"\n";
    }
    else
    {
        cout<<output.size()<<"\n";
        for(ll i = 0; i < (int) output.size(); i++)
        {
            cout<<output[i].size()<<" ";
            for(ll j : output[i])
            {
                cout<<j<<" ";
            }
            cout<<"\n";
        }
    }

    return 0;  
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	216 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	316 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	4 ms	1620 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	220 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	4 ms	724 KB	Output is correct
19	Correct	4 ms	852 KB	Output is correct
20	Correct	2 ms	596 KB	Output is correct
21	Correct	2 ms	468 KB	Output is correct
22	Correct	2 ms	468 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Correct	0 ms	212 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	0 ms	212 KB	Output is correct
37	Correct	0 ms	212 KB	Output is correct

Subtask #4
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	216 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	0 ms	212 KB	Output is correct
37	Correct	0 ms	212 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct
40	Correct	0 ms	212 KB	Output is correct
41	Correct	0 ms	212 KB	Output is correct
42	Correct	0 ms	212 KB	Output is correct
43	Correct	0 ms	212 KB	Output is correct
44	Correct	0 ms	212 KB	Output is correct
45	Correct	0 ms	212 KB	Output is correct
46	Correct	0 ms	212 KB	Output is correct
47	Correct	0 ms	212 KB	Output is correct
48	Correct	0 ms	212 KB	Output is correct
49	Correct	0 ms	212 KB	Output is correct
50	Correct	0 ms	212 KB	Output is correct
51	Correct	0 ms	212 KB	Output is correct
52	Correct	0 ms	212 KB	Output is correct
53	Correct	0 ms	212 KB	Output is correct
54	Correct	0 ms	212 KB	Output is correct
55	Correct	0 ms	212 KB	Output is correct
56	Correct	0 ms	212 KB	Output is correct
57	Correct	0 ms	212 KB	Output is correct
58	Correct	0 ms	212 KB	Output is correct
59	Correct	1 ms	212 KB	Output is correct
60	Correct	0 ms	212 KB	Output is correct
61	Correct	0 ms	212 KB	Output is correct
62	Correct	0 ms	212 KB	Output is correct
63	Correct	1 ms	212 KB	Output is correct
64	Correct	0 ms	212 KB	Output is correct
65	Correct	0 ms	212 KB	Output is correct
66	Correct	1 ms	212 KB	Output is correct
67	Correct	1 ms	340 KB	Output is correct
68	Correct	1 ms	340 KB	Output is correct
69	Correct	0 ms	320 KB	Output is correct
70	Correct	5 ms	340 KB	Output is correct
71	Correct	280 ms	516 KB	Output is correct
72	Correct	45 ms	508 KB	Output is correct
73	Correct	2 ms	348 KB	Output is correct
74	Correct	4 ms	340 KB	Output is correct
75	Correct	30 ms	456 KB	Output is correct
76	Execution timed out	1080 ms	444 KB	Time limit exceeded
77	Halted	0 ms	0 KB	-

Subtask #5
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	216 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	0 ms	212 KB	Output is correct
37	Correct	0 ms	212 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct
40	Correct	0 ms	212 KB	Output is correct
41	Correct	0 ms	212 KB	Output is correct
42	Correct	0 ms	212 KB	Output is correct
43	Correct	0 ms	212 KB	Output is correct
44	Correct	0 ms	212 KB	Output is correct
45	Correct	0 ms	212 KB	Output is correct
46	Correct	0 ms	212 KB	Output is correct
47	Correct	0 ms	212 KB	Output is correct
48	Correct	0 ms	212 KB	Output is correct
49	Correct	0 ms	212 KB	Output is correct
50	Correct	0 ms	212 KB	Output is correct
51	Correct	0 ms	212 KB	Output is correct
52	Correct	0 ms	212 KB	Output is correct
53	Correct	0 ms	212 KB	Output is correct
54	Correct	0 ms	212 KB	Output is correct
55	Correct	0 ms	212 KB	Output is correct
56	Correct	0 ms	212 KB	Output is correct
57	Correct	0 ms	212 KB	Output is correct
58	Correct	0 ms	212 KB	Output is correct
59	Correct	1 ms	212 KB	Output is correct
60	Correct	0 ms	212 KB	Output is correct
61	Correct	0 ms	212 KB	Output is correct
62	Correct	0 ms	212 KB	Output is correct
63	Correct	1 ms	212 KB	Output is correct
64	Correct	0 ms	212 KB	Output is correct
65	Correct	0 ms	212 KB	Output is correct
66	Correct	1 ms	212 KB	Output is correct
67	Correct	1 ms	340 KB	Output is correct
68	Correct	1 ms	340 KB	Output is correct
69	Correct	0 ms	320 KB	Output is correct
70	Correct	5 ms	340 KB	Output is correct
71	Correct	280 ms	516 KB	Output is correct
72	Correct	45 ms	508 KB	Output is correct
73	Correct	2 ms	348 KB	Output is correct
74	Correct	4 ms	340 KB	Output is correct
75	Correct	30 ms	456 KB	Output is correct
76	Execution timed out	1080 ms	444 KB	Time limit exceeded
77	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	216 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	0 ms	316 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	1 ms	320 KB	Output is correct
32	Correct	1 ms	316 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	0 ms	340 KB	Output is correct
37	Correct	1 ms	596 KB	Output is correct
38	Correct	4 ms	1620 KB	Output is correct
39	Correct	0 ms	212 KB	Output is correct
40	Correct	0 ms	212 KB	Output is correct
41	Correct	0 ms	212 KB	Output is correct
42	Correct	0 ms	212 KB	Output is correct
43	Correct	0 ms	212 KB	Output is correct
44	Correct	0 ms	220 KB	Output is correct
45	Correct	0 ms	212 KB	Output is correct
46	Correct	4 ms	724 KB	Output is correct
47	Correct	4 ms	852 KB	Output is correct
48	Correct	2 ms	596 KB	Output is correct
49	Correct	2 ms	468 KB	Output is correct
50	Correct	2 ms	468 KB	Output is correct
51	Correct	0 ms	340 KB	Output is correct
52	Correct	0 ms	212 KB	Output is correct
53	Correct	0 ms	212 KB	Output is correct
54	Correct	0 ms	212 KB	Output is correct
55	Correct	0 ms	212 KB	Output is correct
56	Correct	0 ms	212 KB	Output is correct
57	Correct	0 ms	212 KB	Output is correct
58	Correct	0 ms	212 KB	Output is correct
59	Correct	0 ms	212 KB	Output is correct
60	Correct	0 ms	212 KB	Output is correct
61	Correct	0 ms	212 KB	Output is correct
62	Correct	1 ms	212 KB	Output is correct
63	Correct	0 ms	212 KB	Output is correct
64	Correct	0 ms	212 KB	Output is correct
65	Correct	0 ms	212 KB	Output is correct
66	Correct	0 ms	212 KB	Output is correct
67	Correct	0 ms	212 KB	Output is correct
68	Correct	0 ms	212 KB	Output is correct
69	Correct	0 ms	212 KB	Output is correct
70	Correct	0 ms	212 KB	Output is correct
71	Correct	0 ms	212 KB	Output is correct
72	Correct	0 ms	212 KB	Output is correct
73	Correct	0 ms	212 KB	Output is correct
74	Correct	0 ms	212 KB	Output is correct
75	Correct	0 ms	212 KB	Output is correct
76	Correct	0 ms	212 KB	Output is correct
77	Correct	0 ms	212 KB	Output is correct
78	Correct	0 ms	212 KB	Output is correct
79	Correct	0 ms	212 KB	Output is correct
80	Correct	0 ms	212 KB	Output is correct
81	Correct	0 ms	212 KB	Output is correct
82	Correct	1 ms	212 KB	Output is correct
83	Correct	0 ms	212 KB	Output is correct
84	Correct	0 ms	212 KB	Output is correct
85	Correct	0 ms	212 KB	Output is correct
86	Correct	1 ms	212 KB	Output is correct
87	Correct	0 ms	212 KB	Output is correct
88	Correct	0 ms	212 KB	Output is correct
89	Correct	1 ms	212 KB	Output is correct
90	Correct	1 ms	340 KB	Output is correct
91	Correct	1 ms	340 KB	Output is correct
92	Correct	0 ms	320 KB	Output is correct
93	Correct	5 ms	340 KB	Output is correct
94	Correct	280 ms	516 KB	Output is correct
95	Correct	45 ms	508 KB	Output is correct
96	Correct	2 ms	348 KB	Output is correct
97	Correct	4 ms	340 KB	Output is correct
98	Correct	30 ms	456 KB	Output is correct
99	Execution timed out	1080 ms	444 KB	Time limit exceeded
100	Halted	0 ms	0 KB	-

답안 #804602

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 12.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
7.0 / 7.0

Subtask #3
12.0 / 12.0

Subtask #4
0 / 45.0

Subtask #5
0 / 15.0

Subtask #6
0 / 15.0