답안 #837757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837757	2023-08-25T15:51:59 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;
	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=1; 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=0; 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	273 ms	565760 KB	Output is correct
2	Correct	253 ms	565784 KB	Output is correct
3	Correct	244 ms	565692 KB	Output is correct
4	Correct	235 ms	565792 KB	Output is correct
5	Correct	242 ms	565764 KB	Output is correct
6	Correct	254 ms	565796 KB	Output is correct
7	Correct	238 ms	565824 KB	Output is correct
8	Correct	252 ms	567752 KB	Output is correct
9	Correct	238 ms	567820 KB	Output is correct
10	Correct	238 ms	567884 KB	Output is correct
11	Correct	240 ms	567708 KB	Output is correct
12	Correct	237 ms	567956 KB	Output is correct
13	Correct	239 ms	567884 KB	Output is correct
14	Correct	243 ms	567696 KB	Output is correct
15	Correct	234 ms	567840 KB	Output is correct
16	Correct	238 ms	567836 KB	Output is correct
17	Correct	238 ms	567776 KB	Output is correct
18	Correct	236 ms	567804 KB	Output is correct
19	Correct	242 ms	567844 KB	Output is correct
20	Correct	237 ms	567816 KB	Output is correct
21	Correct	241 ms	567844 KB	Output is correct
22	Correct	242 ms	567788 KB	Output is correct
23	Correct	245 ms	567836 KB	Output is correct
24	Correct	239 ms	567836 KB	Output is correct
25	Correct	243 ms	567744 KB	Output is correct
26	Correct	263 ms	567820 KB	Output is correct
27	Correct	239 ms	567824 KB	Output is correct
28	Correct	240 ms	567732 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	241 ms	565812 KB	Output is correct
2	Correct	239 ms	565756 KB	Output is correct
3	Correct	239 ms	565704 KB	Output is correct
4	Correct	236 ms	565680 KB	Output is correct
5	Correct	240 ms	567788 KB	Output is correct
6	Correct	244 ms	567760 KB	Output is correct
7	Correct	236 ms	565860 KB	Output is correct
8	Correct	253 ms	576640 KB	Output is correct
9	Correct	640 ms	883156 KB	Output is correct
10	Runtime error	982 ms	1048576 KB	Execution killed with signal 11
11	Halted	0 ms	0 KB	-

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	303 ms	565912 KB	Output is correct
2	Correct	267 ms	565852 KB	Output is correct
3	Correct	276 ms	565692 KB	Output is correct
4	Correct	267 ms	565668 KB	Output is correct
5	Correct	276 ms	565720 KB	Output is correct
6	Correct	275 ms	565760 KB	Output is correct
7	Correct	274 ms	565788 KB	Output is correct
8	Correct	265 ms	565756 KB	Output is correct
9	Correct	269 ms	565768 KB	Output is correct
10	Correct	264 ms	565728 KB	Output is correct
11	Correct	261 ms	565800 KB	Output is correct
12	Correct	273 ms	565712 KB	Output is correct
13	Correct	262 ms	565708 KB	Output is correct
14	Correct	266 ms	565688 KB	Output is correct
15	Correct	263 ms	565836 KB	Output is correct
16	Correct	268 ms	565860 KB	Output is correct
17	Correct	278 ms	565920 KB	Output is correct
18	Correct	264 ms	565844 KB	Output is correct
19	Correct	263 ms	565772 KB	Output is correct
20	Correct	272 ms	565812 KB	Output is correct
21	Correct	280 ms	565792 KB	Output is correct
22	Correct	265 ms	565760 KB	Output is correct
23	Correct	270 ms	565856 KB	Output is correct
24	Correct	261 ms	565840 KB	Output is correct
25	Correct	268 ms	565964 KB	Output is correct
26	Correct	265 ms	565772 KB	Output is correct
27	Correct	264 ms	565844 KB	Output is correct
28	Correct	268 ms	565992 KB	Output is correct
29	Correct	265 ms	565852 KB	Output is correct
30	Correct	267 ms	565848 KB	Output is correct
31	Correct	263 ms	565844 KB	Output is correct
32	Correct	267 ms	565952 KB	Output is correct
33	Correct	267 ms	565856 KB	Output is correct
34	Correct	267 ms	565860 KB	Output is correct
35	Correct	277 ms	565856 KB	Output is correct
36	Correct	274 ms	565812 KB	Output is correct
37	Correct	268 ms	565816 KB	Output is correct

Subtask #4
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	273 ms	565760 KB	Output is correct
2	Correct	253 ms	565784 KB	Output is correct
3	Correct	244 ms	565692 KB	Output is correct
4	Correct	235 ms	565792 KB	Output is correct
5	Correct	242 ms	565764 KB	Output is correct
6	Correct	254 ms	565796 KB	Output is correct
7	Correct	238 ms	565824 KB	Output is correct
8	Correct	252 ms	567752 KB	Output is correct
9	Correct	238 ms	567820 KB	Output is correct
10	Correct	238 ms	567884 KB	Output is correct
11	Correct	240 ms	567708 KB	Output is correct
12	Correct	237 ms	567956 KB	Output is correct
13	Correct	239 ms	567884 KB	Output is correct
14	Correct	243 ms	567696 KB	Output is correct
15	Correct	234 ms	567840 KB	Output is correct
16	Correct	238 ms	567836 KB	Output is correct
17	Correct	238 ms	567776 KB	Output is correct
18	Correct	236 ms	567804 KB	Output is correct
19	Correct	242 ms	567844 KB	Output is correct
20	Correct	237 ms	567816 KB	Output is correct
21	Correct	241 ms	567844 KB	Output is correct
22	Correct	242 ms	567788 KB	Output is correct
23	Correct	245 ms	567836 KB	Output is correct
24	Correct	239 ms	567836 KB	Output is correct
25	Correct	243 ms	567744 KB	Output is correct
26	Correct	263 ms	567820 KB	Output is correct
27	Correct	239 ms	567824 KB	Output is correct
28	Correct	240 ms	567732 KB	Output is correct
29	Correct	303 ms	565912 KB	Output is correct
30	Correct	267 ms	565852 KB	Output is correct
31	Correct	276 ms	565692 KB	Output is correct
32	Correct	267 ms	565668 KB	Output is correct
33	Correct	276 ms	565720 KB	Output is correct
34	Correct	275 ms	565760 KB	Output is correct
35	Correct	274 ms	565788 KB	Output is correct
36	Correct	265 ms	565756 KB	Output is correct
37	Correct	269 ms	565768 KB	Output is correct
38	Correct	264 ms	565728 KB	Output is correct
39	Correct	261 ms	565800 KB	Output is correct
40	Correct	273 ms	565712 KB	Output is correct
41	Correct	262 ms	565708 KB	Output is correct
42	Correct	266 ms	565688 KB	Output is correct
43	Correct	263 ms	565836 KB	Output is correct
44	Correct	268 ms	565860 KB	Output is correct
45	Correct	278 ms	565920 KB	Output is correct
46	Correct	264 ms	565844 KB	Output is correct
47	Correct	263 ms	565772 KB	Output is correct
48	Correct	272 ms	565812 KB	Output is correct
49	Correct	280 ms	565792 KB	Output is correct
50	Correct	265 ms	565760 KB	Output is correct
51	Correct	270 ms	565856 KB	Output is correct
52	Correct	261 ms	565840 KB	Output is correct
53	Correct	268 ms	565964 KB	Output is correct
54	Correct	265 ms	565772 KB	Output is correct
55	Correct	264 ms	565844 KB	Output is correct
56	Correct	268 ms	565992 KB	Output is correct
57	Correct	265 ms	565852 KB	Output is correct
58	Correct	267 ms	565848 KB	Output is correct
59	Correct	263 ms	565844 KB	Output is correct
60	Correct	267 ms	565952 KB	Output is correct
61	Correct	267 ms	565856 KB	Output is correct
62	Correct	267 ms	565860 KB	Output is correct
63	Correct	277 ms	565856 KB	Output is correct
64	Correct	274 ms	565812 KB	Output is correct
65	Correct	268 ms	565816 KB	Output is correct
66	Correct	268 ms	565836 KB	Output is correct
67	Correct	271 ms	576608 KB	Output is correct
68	Correct	263 ms	567948 KB	Output is correct
69	Correct	276 ms	568100 KB	Output is correct
70	Correct	277 ms	568324 KB	Output is correct
71	Correct	299 ms	568196 KB	Output is correct
72	Correct	266 ms	568068 KB	Output is correct
73	Correct	268 ms	567944 KB	Output is correct
74	Correct	270 ms	568064 KB	Output is correct
75	Correct	274 ms	567924 KB	Output is correct
76	Correct	274 ms	569784 KB	Output is correct
77	Correct	275 ms	568748 KB	Output is correct
78	Correct	269 ms	569808 KB	Output is correct
79	Correct	315 ms	569804 KB	Output is correct
80	Correct	270 ms	569924 KB	Output is correct
81	Correct	275 ms	568268 KB	Output is correct
82	Correct	278 ms	569036 KB	Output is correct
83	Correct	267 ms	567884 KB	Output is correct
84	Correct	282 ms	568232 KB	Output is correct
85	Correct	281 ms	568068 KB	Output is correct
86	Correct	275 ms	568264 KB	Output is correct
87	Correct	269 ms	568252 KB	Output is correct
88	Correct	271 ms	568300 KB	Output is correct
89	Correct	265 ms	568112 KB	Output is correct
90	Correct	280 ms	568256 KB	Output is correct
91	Correct	268 ms	568028 KB	Output is correct
92	Correct	273 ms	568296 KB	Output is correct
93	Correct	288 ms	569832 KB	Output is correct
94	Correct	274 ms	569688 KB	Output is correct
95	Correct	277 ms	569316 KB	Output is correct
96	Correct	276 ms	568496 KB	Output is correct
97	Correct	271 ms	568120 KB	Output is correct

Subtask #5
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	273 ms	565760 KB	Output is correct
2	Correct	253 ms	565784 KB	Output is correct
3	Correct	244 ms	565692 KB	Output is correct
4	Correct	235 ms	565792 KB	Output is correct
5	Correct	242 ms	565764 KB	Output is correct
6	Correct	254 ms	565796 KB	Output is correct
7	Correct	238 ms	565824 KB	Output is correct
8	Correct	252 ms	567752 KB	Output is correct
9	Correct	238 ms	567820 KB	Output is correct
10	Correct	238 ms	567884 KB	Output is correct
11	Correct	240 ms	567708 KB	Output is correct
12	Correct	237 ms	567956 KB	Output is correct
13	Correct	239 ms	567884 KB	Output is correct
14	Correct	243 ms	567696 KB	Output is correct
15	Correct	234 ms	567840 KB	Output is correct
16	Correct	238 ms	567836 KB	Output is correct
17	Correct	238 ms	567776 KB	Output is correct
18	Correct	236 ms	567804 KB	Output is correct
19	Correct	242 ms	567844 KB	Output is correct
20	Correct	237 ms	567816 KB	Output is correct
21	Correct	241 ms	567844 KB	Output is correct
22	Correct	242 ms	567788 KB	Output is correct
23	Correct	245 ms	567836 KB	Output is correct
24	Correct	239 ms	567836 KB	Output is correct
25	Correct	243 ms	567744 KB	Output is correct
26	Correct	263 ms	567820 KB	Output is correct
27	Correct	239 ms	567824 KB	Output is correct
28	Correct	240 ms	567732 KB	Output is correct
29	Correct	303 ms	565912 KB	Output is correct
30	Correct	267 ms	565852 KB	Output is correct
31	Correct	276 ms	565692 KB	Output is correct
32	Correct	267 ms	565668 KB	Output is correct
33	Correct	276 ms	565720 KB	Output is correct
34	Correct	275 ms	565760 KB	Output is correct
35	Correct	274 ms	565788 KB	Output is correct
36	Correct	265 ms	565756 KB	Output is correct
37	Correct	269 ms	565768 KB	Output is correct
38	Correct	264 ms	565728 KB	Output is correct
39	Correct	261 ms	565800 KB	Output is correct
40	Correct	273 ms	565712 KB	Output is correct
41	Correct	262 ms	565708 KB	Output is correct
42	Correct	266 ms	565688 KB	Output is correct
43	Correct	263 ms	565836 KB	Output is correct
44	Correct	268 ms	565860 KB	Output is correct
45	Correct	278 ms	565920 KB	Output is correct
46	Correct	264 ms	565844 KB	Output is correct
47	Correct	263 ms	565772 KB	Output is correct
48	Correct	272 ms	565812 KB	Output is correct
49	Correct	280 ms	565792 KB	Output is correct
50	Correct	265 ms	565760 KB	Output is correct
51	Correct	270 ms	565856 KB	Output is correct
52	Correct	261 ms	565840 KB	Output is correct
53	Correct	268 ms	565964 KB	Output is correct
54	Correct	265 ms	565772 KB	Output is correct
55	Correct	264 ms	565844 KB	Output is correct
56	Correct	268 ms	565992 KB	Output is correct
57	Correct	265 ms	565852 KB	Output is correct
58	Correct	267 ms	565848 KB	Output is correct
59	Correct	263 ms	565844 KB	Output is correct
60	Correct	267 ms	565952 KB	Output is correct
61	Correct	267 ms	565856 KB	Output is correct
62	Correct	267 ms	565860 KB	Output is correct
63	Correct	277 ms	565856 KB	Output is correct
64	Correct	274 ms	565812 KB	Output is correct
65	Correct	268 ms	565816 KB	Output is correct
66	Correct	268 ms	565836 KB	Output is correct
67	Correct	271 ms	576608 KB	Output is correct
68	Correct	263 ms	567948 KB	Output is correct
69	Correct	276 ms	568100 KB	Output is correct
70	Correct	277 ms	568324 KB	Output is correct
71	Correct	299 ms	568196 KB	Output is correct
72	Correct	266 ms	568068 KB	Output is correct
73	Correct	268 ms	567944 KB	Output is correct
74	Correct	270 ms	568064 KB	Output is correct
75	Correct	274 ms	567924 KB	Output is correct
76	Correct	274 ms	569784 KB	Output is correct
77	Correct	275 ms	568748 KB	Output is correct
78	Correct	269 ms	569808 KB	Output is correct
79	Correct	315 ms	569804 KB	Output is correct
80	Correct	270 ms	569924 KB	Output is correct
81	Correct	275 ms	568268 KB	Output is correct
82	Correct	278 ms	569036 KB	Output is correct
83	Correct	267 ms	567884 KB	Output is correct
84	Correct	282 ms	568232 KB	Output is correct
85	Correct	281 ms	568068 KB	Output is correct
86	Correct	275 ms	568264 KB	Output is correct
87	Correct	269 ms	568252 KB	Output is correct
88	Correct	271 ms	568300 KB	Output is correct
89	Correct	265 ms	568112 KB	Output is correct
90	Correct	280 ms	568256 KB	Output is correct
91	Correct	268 ms	568028 KB	Output is correct
92	Correct	273 ms	568296 KB	Output is correct
93	Correct	288 ms	569832 KB	Output is correct
94	Correct	274 ms	569688 KB	Output is correct
95	Correct	277 ms	569316 KB	Output is correct
96	Correct	276 ms	568496 KB	Output is correct
97	Correct	271 ms	568120 KB	Output is correct
98	Correct	624 ms	883192 KB	Output is correct
99	Correct	269 ms	569772 KB	Output is correct
100	Correct	366 ms	618668 KB	Output is correct
101	Correct	307 ms	587928 KB	Output is correct
102	Correct	301 ms	580328 KB	Output is correct
103	Correct	302 ms	584452 KB	Output is correct
104	Correct	285 ms	581020 KB	Output is correct
105	Correct	334 ms	590320 KB	Output is correct
106	Execution timed out	1131 ms	656008 KB	Time limit exceeded
107	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	273 ms	565760 KB	Output is correct
2	Correct	253 ms	565784 KB	Output is correct
3	Correct	244 ms	565692 KB	Output is correct
4	Correct	235 ms	565792 KB	Output is correct
5	Correct	242 ms	565764 KB	Output is correct
6	Correct	254 ms	565796 KB	Output is correct
7	Correct	238 ms	565824 KB	Output is correct
8	Correct	252 ms	567752 KB	Output is correct
9	Correct	238 ms	567820 KB	Output is correct
10	Correct	238 ms	567884 KB	Output is correct
11	Correct	240 ms	567708 KB	Output is correct
12	Correct	237 ms	567956 KB	Output is correct
13	Correct	239 ms	567884 KB	Output is correct
14	Correct	243 ms	567696 KB	Output is correct
15	Correct	234 ms	567840 KB	Output is correct
16	Correct	238 ms	567836 KB	Output is correct
17	Correct	238 ms	567776 KB	Output is correct
18	Correct	236 ms	567804 KB	Output is correct
19	Correct	242 ms	567844 KB	Output is correct
20	Correct	237 ms	567816 KB	Output is correct
21	Correct	241 ms	567844 KB	Output is correct
22	Correct	242 ms	567788 KB	Output is correct
23	Correct	245 ms	567836 KB	Output is correct
24	Correct	239 ms	567836 KB	Output is correct
25	Correct	243 ms	567744 KB	Output is correct
26	Correct	263 ms	567820 KB	Output is correct
27	Correct	239 ms	567824 KB	Output is correct
28	Correct	240 ms	567732 KB	Output is correct
29	Correct	241 ms	565812 KB	Output is correct
30	Correct	239 ms	565756 KB	Output is correct
31	Correct	239 ms	565704 KB	Output is correct
32	Correct	236 ms	565680 KB	Output is correct
33	Correct	240 ms	567788 KB	Output is correct
34	Correct	244 ms	567760 KB	Output is correct
35	Correct	236 ms	565860 KB	Output is correct
36	Correct	253 ms	576640 KB	Output is correct
37	Correct	640 ms	883156 KB	Output is correct
38	Runtime error	982 ms	1048576 KB	Execution killed with signal 11
39	Halted	0 ms	0 KB	-

답안 #837757

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