답안 #837763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837763	2023-08-25T16:08:28 Z	Antekb	Cookies (JOI23_cookies)	C++17	63 / 100	1000 ms	1048576 KB

#include<bits/stdc++.h>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
using ld = long double;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t)){
		cerr<<", ";
	}
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=3005;
vi par[N][N];
vector<bool> par2[N][N];
int opt[N], tim[N], ile[N], str[N][N];
int main(){
	int n, m;
	cin>>n;
	vii V(n);
	int M=0;
	for(int i=0;i<n; i++){
		cin>>V[i].st;
		M=max(M, V[i].st);
		for(int j=0; j<V[i].st; j++)ile[j]++;
		V[i].nd=i+1;
	}
	sort(all(V));
	int s=0;
	for(int i=0; i<M; i++){
		for(int j=s; j<s+ile[M-i-1]; j++){
			tim[j]=i;
		}
		s+=ile[M-i-1];
	}
	tim[s]=M;
	for(int i=1; i<=s; i++){
		opt[i]=-1e9;
		//deb(i, tim[i]);
	}
	cin>>m;
	vi V2(m);
	for(int &i:V2){
		cin>>i;
	}
	sort(all(V2));
	for(int i=0; i<=s; i++){
		for(int j=0; j<=M; j++){
			str[i][j]=1e9;
		}
	}
	str[0][0]=0;
	opt[0]=0;
	int C=100;
	for(int c:V2){
		for(int i=c; i<=s; i++){
			if(opt[i]<min(opt[i-c]+1, tim[i])){
				opt[i]=min(opt[i-c]+1, tim[i]);
			}
			for(int j=max(1, opt[i]-C); j<=opt[i]; j++){
				if(str[i][j]>str[i-c][j-1]){
					str[i][j]=str[i-c][j-1];
					par[i][j].pb(c);
					par2[i][j].pb(0);
				}
			}
			for(int j=max(0, opt[i]-C); j<=opt[i]; j++){
				if(str[i][j]>str[i-c][j]+1){
					str[i][j]=str[i-c][j]+1;
					par[i][j].pb(c);
					par2[i][j].pb(1);
				}
			}
		}
		//for(int i=0; i<=s; i++){deb(i, tim[i], opt[i]);}
		/*cout<<c<<"\n";
		for(int i=0; i<=s; i++){
			deb(i, opt[i], tim[i]);
			for(int j=0; j<=opt[i]; j++){
				cout<<str[i][j]<<" ";
			}
			cout<<"\n";
		}*/
	}
	if(opt[s]!=M){
		cout<<-1;
		return 0;
	}
	vi siz;
	int prv=1e9;
	int j=M;
	while(s){
		//deb(s,j,str[s][j]);
		//deb(par[s][j].size());
		while(par[s][j].back()>prv){
			par[s][j].pp();
			par2[s][j].pp();
		}
		int jj=par2[s][j].back();
		prv=par[s][j].back();
		//deb(prv, jj);
		siz.pb(prv);
		s-=prv;
		j-=1-jj;
	}
	cout<<siz.size()<<"\n";
	//for(int i:siz)cout<<i<<" ";
	//return 0;
	priority_queue<pair<int, int> > Q;
	for(auto &i:V)Q.push(i);
	for(int j:siz){
		cout<<j<<" ";
		vii todo;
		for(int i=0; i<j; i++){
			assert(Q.size());
			todo.pb(Q.top());
			Q.pop();
			cout<<todo.back().nd<<" ";
			todo.back().st--;
		}
		cout<<"\n";
		for(auto i:todo){
			if(i.st)Q.push(i);
		}
	}
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	245 ms	565844 KB	Output is correct
2	Correct	225 ms	565708 KB	Output is correct
3	Correct	227 ms	565796 KB	Output is correct
4	Correct	223 ms	565740 KB	Output is correct
5	Correct	227 ms	565812 KB	Output is correct
6	Correct	219 ms	565752 KB	Output is correct
7	Correct	226 ms	565836 KB	Output is correct
8	Correct	229 ms	567756 KB	Output is correct
9	Correct	223 ms	567828 KB	Output is correct
10	Correct	226 ms	567920 KB	Output is correct
11	Correct	222 ms	567828 KB	Output is correct
12	Correct	235 ms	567960 KB	Output is correct
13	Correct	240 ms	567884 KB	Output is correct
14	Correct	222 ms	567724 KB	Output is correct
15	Correct	227 ms	567756 KB	Output is correct
16	Correct	222 ms	567836 KB	Output is correct
17	Correct	225 ms	567756 KB	Output is correct
18	Correct	225 ms	567780 KB	Output is correct
19	Correct	230 ms	567800 KB	Output is correct
20	Correct	222 ms	567756 KB	Output is correct
21	Correct	226 ms	567884 KB	Output is correct
22	Correct	222 ms	567732 KB	Output is correct
23	Correct	231 ms	567756 KB	Output is correct
24	Correct	221 ms	567828 KB	Output is correct
25	Correct	225 ms	567756 KB	Output is correct
26	Correct	222 ms	567816 KB	Output is correct
27	Correct	223 ms	567812 KB	Output is correct
28	Correct	222 ms	567752 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	231 ms	565968 KB	Output is correct
2	Correct	243 ms	565796 KB	Output is correct
3	Correct	227 ms	565708 KB	Output is correct
4	Correct	221 ms	565792 KB	Output is correct
5	Correct	232 ms	567848 KB	Output is correct
6	Correct	233 ms	567824 KB	Output is correct
7	Correct	234 ms	565856 KB	Output is correct
8	Correct	227 ms	571596 KB	Output is correct
9	Correct	275 ms	619852 KB	Output is correct
10	Execution timed out	1090 ms	1048576 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	227 ms	565728 KB	Output is correct
2	Correct	225 ms	565844 KB	Output is correct
3	Correct	228 ms	565772 KB	Output is correct
4	Correct	224 ms	565704 KB	Output is correct
5	Correct	229 ms	565736 KB	Output is correct
6	Correct	246 ms	565740 KB	Output is correct
7	Correct	230 ms	565712 KB	Output is correct
8	Correct	223 ms	565708 KB	Output is correct
9	Correct	243 ms	565928 KB	Output is correct
10	Correct	221 ms	565740 KB	Output is correct
11	Correct	221 ms	565752 KB	Output is correct
12	Correct	223 ms	565748 KB	Output is correct
13	Correct	233 ms	565804 KB	Output is correct
14	Correct	223 ms	565808 KB	Output is correct
15	Correct	232 ms	565808 KB	Output is correct
16	Correct	223 ms	565856 KB	Output is correct
17	Correct	227 ms	565836 KB	Output is correct
18	Correct	228 ms	565820 KB	Output is correct
19	Correct	239 ms	565832 KB	Output is correct
20	Correct	227 ms	565836 KB	Output is correct
21	Correct	233 ms	565840 KB	Output is correct
22	Correct	230 ms	565848 KB	Output is correct
23	Correct	226 ms	565824 KB	Output is correct
24	Correct	231 ms	565840 KB	Output is correct
25	Correct	229 ms	565876 KB	Output is correct
26	Correct	230 ms	565836 KB	Output is correct
27	Correct	236 ms	565812 KB	Output is correct
28	Correct	229 ms	565816 KB	Output is correct
29	Correct	226 ms	565968 KB	Output is correct
30	Correct	229 ms	565820 KB	Output is correct
31	Correct	231 ms	565852 KB	Output is correct
32	Correct	231 ms	565852 KB	Output is correct
33	Correct	228 ms	565836 KB	Output is correct
34	Correct	229 ms	565756 KB	Output is correct
35	Correct	222 ms	565736 KB	Output is correct
36	Correct	222 ms	565852 KB	Output is correct
37	Correct	228 ms	565736 KB	Output is correct

Subtask #4
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	245 ms	565844 KB	Output is correct
2	Correct	225 ms	565708 KB	Output is correct
3	Correct	227 ms	565796 KB	Output is correct
4	Correct	223 ms	565740 KB	Output is correct
5	Correct	227 ms	565812 KB	Output is correct
6	Correct	219 ms	565752 KB	Output is correct
7	Correct	226 ms	565836 KB	Output is correct
8	Correct	229 ms	567756 KB	Output is correct
9	Correct	223 ms	567828 KB	Output is correct
10	Correct	226 ms	567920 KB	Output is correct
11	Correct	222 ms	567828 KB	Output is correct
12	Correct	235 ms	567960 KB	Output is correct
13	Correct	240 ms	567884 KB	Output is correct
14	Correct	222 ms	567724 KB	Output is correct
15	Correct	227 ms	567756 KB	Output is correct
16	Correct	222 ms	567836 KB	Output is correct
17	Correct	225 ms	567756 KB	Output is correct
18	Correct	225 ms	567780 KB	Output is correct
19	Correct	230 ms	567800 KB	Output is correct
20	Correct	222 ms	567756 KB	Output is correct
21	Correct	226 ms	567884 KB	Output is correct
22	Correct	222 ms	567732 KB	Output is correct
23	Correct	231 ms	567756 KB	Output is correct
24	Correct	221 ms	567828 KB	Output is correct
25	Correct	225 ms	567756 KB	Output is correct
26	Correct	222 ms	567816 KB	Output is correct
27	Correct	223 ms	567812 KB	Output is correct
28	Correct	222 ms	567752 KB	Output is correct
29	Correct	227 ms	565728 KB	Output is correct
30	Correct	225 ms	565844 KB	Output is correct
31	Correct	228 ms	565772 KB	Output is correct
32	Correct	224 ms	565704 KB	Output is correct
33	Correct	229 ms	565736 KB	Output is correct
34	Correct	246 ms	565740 KB	Output is correct
35	Correct	230 ms	565712 KB	Output is correct
36	Correct	223 ms	565708 KB	Output is correct
37	Correct	243 ms	565928 KB	Output is correct
38	Correct	221 ms	565740 KB	Output is correct
39	Correct	221 ms	565752 KB	Output is correct
40	Correct	223 ms	565748 KB	Output is correct
41	Correct	233 ms	565804 KB	Output is correct
42	Correct	223 ms	565808 KB	Output is correct
43	Correct	232 ms	565808 KB	Output is correct
44	Correct	223 ms	565856 KB	Output is correct
45	Correct	227 ms	565836 KB	Output is correct
46	Correct	228 ms	565820 KB	Output is correct
47	Correct	239 ms	565832 KB	Output is correct
48	Correct	227 ms	565836 KB	Output is correct
49	Correct	233 ms	565840 KB	Output is correct
50	Correct	230 ms	565848 KB	Output is correct
51	Correct	226 ms	565824 KB	Output is correct
52	Correct	231 ms	565840 KB	Output is correct
53	Correct	229 ms	565876 KB	Output is correct
54	Correct	230 ms	565836 KB	Output is correct
55	Correct	236 ms	565812 KB	Output is correct
56	Correct	229 ms	565816 KB	Output is correct
57	Correct	226 ms	565968 KB	Output is correct
58	Correct	229 ms	565820 KB	Output is correct
59	Correct	231 ms	565852 KB	Output is correct
60	Correct	231 ms	565852 KB	Output is correct
61	Correct	228 ms	565836 KB	Output is correct
62	Correct	229 ms	565756 KB	Output is correct
63	Correct	222 ms	565736 KB	Output is correct
64	Correct	222 ms	565852 KB	Output is correct
65	Correct	228 ms	565736 KB	Output is correct
66	Correct	224 ms	565964 KB	Output is correct
67	Correct	234 ms	571596 KB	Output is correct
68	Correct	250 ms	567984 KB	Output is correct
69	Correct	230 ms	567976 KB	Output is correct
70	Correct	234 ms	568324 KB	Output is correct
71	Correct	227 ms	568116 KB	Output is correct
72	Correct	244 ms	568112 KB	Output is correct
73	Correct	224 ms	567964 KB	Output is correct
74	Correct	228 ms	567996 KB	Output is correct
75	Correct	222 ms	568012 KB	Output is correct
76	Correct	232 ms	569712 KB	Output is correct
77	Correct	233 ms	568780 KB	Output is correct
78	Correct	233 ms	569820 KB	Output is correct
79	Correct	236 ms	569772 KB	Output is correct
80	Correct	229 ms	570028 KB	Output is correct
81	Correct	234 ms	568308 KB	Output is correct
82	Correct	222 ms	568964 KB	Output is correct
83	Correct	245 ms	567960 KB	Output is correct
84	Correct	251 ms	568224 KB	Output is correct
85	Correct	256 ms	568008 KB	Output is correct
86	Correct	225 ms	568316 KB	Output is correct
87	Correct	220 ms	568312 KB	Output is correct
88	Correct	258 ms	568384 KB	Output is correct
89	Correct	231 ms	568116 KB	Output is correct
90	Correct	233 ms	568128 KB	Output is correct
91	Correct	228 ms	568116 KB	Output is correct
92	Correct	231 ms	568376 KB	Output is correct
93	Correct	273 ms	569764 KB	Output is correct
94	Correct	311 ms	569788 KB	Output is correct
95	Correct	229 ms	569108 KB	Output is correct
96	Correct	243 ms	568544 KB	Output is correct
97	Correct	228 ms	568180 KB	Output is correct

Subtask #5
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	245 ms	565844 KB	Output is correct
2	Correct	225 ms	565708 KB	Output is correct
3	Correct	227 ms	565796 KB	Output is correct
4	Correct	223 ms	565740 KB	Output is correct
5	Correct	227 ms	565812 KB	Output is correct
6	Correct	219 ms	565752 KB	Output is correct
7	Correct	226 ms	565836 KB	Output is correct
8	Correct	229 ms	567756 KB	Output is correct
9	Correct	223 ms	567828 KB	Output is correct
10	Correct	226 ms	567920 KB	Output is correct
11	Correct	222 ms	567828 KB	Output is correct
12	Correct	235 ms	567960 KB	Output is correct
13	Correct	240 ms	567884 KB	Output is correct
14	Correct	222 ms	567724 KB	Output is correct
15	Correct	227 ms	567756 KB	Output is correct
16	Correct	222 ms	567836 KB	Output is correct
17	Correct	225 ms	567756 KB	Output is correct
18	Correct	225 ms	567780 KB	Output is correct
19	Correct	230 ms	567800 KB	Output is correct
20	Correct	222 ms	567756 KB	Output is correct
21	Correct	226 ms	567884 KB	Output is correct
22	Correct	222 ms	567732 KB	Output is correct
23	Correct	231 ms	567756 KB	Output is correct
24	Correct	221 ms	567828 KB	Output is correct
25	Correct	225 ms	567756 KB	Output is correct
26	Correct	222 ms	567816 KB	Output is correct
27	Correct	223 ms	567812 KB	Output is correct
28	Correct	222 ms	567752 KB	Output is correct
29	Correct	227 ms	565728 KB	Output is correct
30	Correct	225 ms	565844 KB	Output is correct
31	Correct	228 ms	565772 KB	Output is correct
32	Correct	224 ms	565704 KB	Output is correct
33	Correct	229 ms	565736 KB	Output is correct
34	Correct	246 ms	565740 KB	Output is correct
35	Correct	230 ms	565712 KB	Output is correct
36	Correct	223 ms	565708 KB	Output is correct
37	Correct	243 ms	565928 KB	Output is correct
38	Correct	221 ms	565740 KB	Output is correct
39	Correct	221 ms	565752 KB	Output is correct
40	Correct	223 ms	565748 KB	Output is correct
41	Correct	233 ms	565804 KB	Output is correct
42	Correct	223 ms	565808 KB	Output is correct
43	Correct	232 ms	565808 KB	Output is correct
44	Correct	223 ms	565856 KB	Output is correct
45	Correct	227 ms	565836 KB	Output is correct
46	Correct	228 ms	565820 KB	Output is correct
47	Correct	239 ms	565832 KB	Output is correct
48	Correct	227 ms	565836 KB	Output is correct
49	Correct	233 ms	565840 KB	Output is correct
50	Correct	230 ms	565848 KB	Output is correct
51	Correct	226 ms	565824 KB	Output is correct
52	Correct	231 ms	565840 KB	Output is correct
53	Correct	229 ms	565876 KB	Output is correct
54	Correct	230 ms	565836 KB	Output is correct
55	Correct	236 ms	565812 KB	Output is correct
56	Correct	229 ms	565816 KB	Output is correct
57	Correct	226 ms	565968 KB	Output is correct
58	Correct	229 ms	565820 KB	Output is correct
59	Correct	231 ms	565852 KB	Output is correct
60	Correct	231 ms	565852 KB	Output is correct
61	Correct	228 ms	565836 KB	Output is correct
62	Correct	229 ms	565756 KB	Output is correct
63	Correct	222 ms	565736 KB	Output is correct
64	Correct	222 ms	565852 KB	Output is correct
65	Correct	228 ms	565736 KB	Output is correct
66	Correct	224 ms	565964 KB	Output is correct
67	Correct	234 ms	571596 KB	Output is correct
68	Correct	250 ms	567984 KB	Output is correct
69	Correct	230 ms	567976 KB	Output is correct
70	Correct	234 ms	568324 KB	Output is correct
71	Correct	227 ms	568116 KB	Output is correct
72	Correct	244 ms	568112 KB	Output is correct
73	Correct	224 ms	567964 KB	Output is correct
74	Correct	228 ms	567996 KB	Output is correct
75	Correct	222 ms	568012 KB	Output is correct
76	Correct	232 ms	569712 KB	Output is correct
77	Correct	233 ms	568780 KB	Output is correct
78	Correct	233 ms	569820 KB	Output is correct
79	Correct	236 ms	569772 KB	Output is correct
80	Correct	229 ms	570028 KB	Output is correct
81	Correct	234 ms	568308 KB	Output is correct
82	Correct	222 ms	568964 KB	Output is correct
83	Correct	245 ms	567960 KB	Output is correct
84	Correct	251 ms	568224 KB	Output is correct
85	Correct	256 ms	568008 KB	Output is correct
86	Correct	225 ms	568316 KB	Output is correct
87	Correct	220 ms	568312 KB	Output is correct
88	Correct	258 ms	568384 KB	Output is correct
89	Correct	231 ms	568116 KB	Output is correct
90	Correct	233 ms	568128 KB	Output is correct
91	Correct	228 ms	568116 KB	Output is correct
92	Correct	231 ms	568376 KB	Output is correct
93	Correct	273 ms	569764 KB	Output is correct
94	Correct	311 ms	569788 KB	Output is correct
95	Correct	229 ms	569108 KB	Output is correct
96	Correct	243 ms	568544 KB	Output is correct
97	Correct	228 ms	568180 KB	Output is correct
98	Correct	272 ms	619704 KB	Output is correct
99	Correct	228 ms	569776 KB	Output is correct
100	Correct	296 ms	608428 KB	Output is correct
101	Correct	264 ms	588024 KB	Output is correct
102	Correct	242 ms	580352 KB	Output is correct
103	Correct	251 ms	584448 KB	Output is correct
104	Correct	241 ms	580980 KB	Output is correct
105	Correct	299 ms	590280 KB	Output is correct
106	Execution timed out	1069 ms	611248 KB	Time limit exceeded
107	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	245 ms	565844 KB	Output is correct
2	Correct	225 ms	565708 KB	Output is correct
3	Correct	227 ms	565796 KB	Output is correct
4	Correct	223 ms	565740 KB	Output is correct
5	Correct	227 ms	565812 KB	Output is correct
6	Correct	219 ms	565752 KB	Output is correct
7	Correct	226 ms	565836 KB	Output is correct
8	Correct	229 ms	567756 KB	Output is correct
9	Correct	223 ms	567828 KB	Output is correct
10	Correct	226 ms	567920 KB	Output is correct
11	Correct	222 ms	567828 KB	Output is correct
12	Correct	235 ms	567960 KB	Output is correct
13	Correct	240 ms	567884 KB	Output is correct
14	Correct	222 ms	567724 KB	Output is correct
15	Correct	227 ms	567756 KB	Output is correct
16	Correct	222 ms	567836 KB	Output is correct
17	Correct	225 ms	567756 KB	Output is correct
18	Correct	225 ms	567780 KB	Output is correct
19	Correct	230 ms	567800 KB	Output is correct
20	Correct	222 ms	567756 KB	Output is correct
21	Correct	226 ms	567884 KB	Output is correct
22	Correct	222 ms	567732 KB	Output is correct
23	Correct	231 ms	567756 KB	Output is correct
24	Correct	221 ms	567828 KB	Output is correct
25	Correct	225 ms	567756 KB	Output is correct
26	Correct	222 ms	567816 KB	Output is correct
27	Correct	223 ms	567812 KB	Output is correct
28	Correct	222 ms	567752 KB	Output is correct
29	Correct	231 ms	565968 KB	Output is correct
30	Correct	243 ms	565796 KB	Output is correct
31	Correct	227 ms	565708 KB	Output is correct
32	Correct	221 ms	565792 KB	Output is correct
33	Correct	232 ms	567848 KB	Output is correct
34	Correct	233 ms	567824 KB	Output is correct
35	Correct	234 ms	565856 KB	Output is correct
36	Correct	227 ms	571596 KB	Output is correct
37	Correct	275 ms	619852 KB	Output is correct
38	Execution timed out	1090 ms	1048576 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-

답안 #837763

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 0 / 7.0

Subtask #3 12.0 / 12.0

Subtask #4 45.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
12.0 / 12.0

Subtask #4
45.0 / 45.0

Subtask #5
0 / 15.0

Subtask #6
0 / 15.0