oj.uz

Submission #837765

# Submission time Handle Problem Language Result Execution time Memory
837765 2023-08-25T16:09:51 Z Antekb Cookies (JOI23_cookies) C++17
78 / 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=50;
	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

# Verdict Execution time Memory Grader output
1 Correct 230 ms 565716 KB Output is correct
2 Correct 236 ms 565788 KB Output is correct
3 Correct 223 ms 565800 KB Output is correct
4 Correct 225 ms 565748 KB Output is correct
5 Correct 227 ms 565708 KB Output is correct
6 Correct 230 ms 565708 KB Output is correct
7 Correct 221 ms 565812 KB Output is correct
8 Correct 233 ms 567748 KB Output is correct
9 Correct 221 ms 567756 KB Output is correct
10 Correct 222 ms 567884 KB Output is correct
11 Correct 242 ms 567740 KB Output is correct
12 Correct 221 ms 567948 KB Output is correct
13 Correct 232 ms 567808 KB Output is correct
14 Correct 234 ms 567700 KB Output is correct
15 Correct 231 ms 567832 KB Output is correct
16 Correct 225 ms 567812 KB Output is correct
17 Correct 243 ms 567844 KB Output is correct
18 Correct 226 ms 567796 KB Output is correct
19 Correct 234 ms 567836 KB Output is correct
20 Correct 232 ms 567816 KB Output is correct
21 Correct 236 ms 567896 KB Output is correct
22 Correct 228 ms 567800 KB Output is correct
23 Correct 236 ms 567756 KB Output is correct
24 Correct 226 ms 567712 KB Output is correct
25 Correct 240 ms 567824 KB Output is correct
26 Correct 244 ms 567756 KB Output is correct
27 Correct 228 ms 567712 KB Output is correct
28 Correct 238 ms 567756 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 565752 KB Output is correct
2 Correct 240 ms 565708 KB Output is correct
3 Correct 237 ms 565908 KB Output is correct
4 Correct 238 ms 565816 KB Output is correct
5 Correct 232 ms 567844 KB Output is correct
6 Correct 230 ms 567756 KB Output is correct
7 Correct 230 ms 565828 KB Output is correct
8 Correct 232 ms 570296 KB Output is correct
9 Correct 267 ms 610596 KB Output is correct
10 Execution timed out 1139 ms 1048576 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 565812 KB Output is correct
2 Correct 231 ms 565780 KB Output is correct
3 Correct 229 ms 565724 KB Output is correct
4 Correct 233 ms 565684 KB Output is correct
5 Correct 234 ms 565792 KB Output is correct
6 Correct 228 ms 565676 KB Output is correct
7 Correct 234 ms 565796 KB Output is correct
8 Correct 226 ms 565708 KB Output is correct
9 Correct 251 ms 565768 KB Output is correct
10 Correct 226 ms 565708 KB Output is correct
11 Correct 234 ms 565776 KB Output is correct
12 Correct 249 ms 565784 KB Output is correct
13 Correct 232 ms 565788 KB Output is correct
14 Correct 234 ms 565788 KB Output is correct
15 Correct 235 ms 565860 KB Output is correct
16 Correct 231 ms 565796 KB Output is correct
17 Correct 233 ms 565848 KB Output is correct
18 Correct 241 ms 565824 KB Output is correct
19 Correct 230 ms 565812 KB Output is correct
20 Correct 234 ms 565836 KB Output is correct
21 Correct 227 ms 565844 KB Output is correct
22 Correct 243 ms 565852 KB Output is correct
23 Correct 232 ms 565832 KB Output is correct
24 Correct 233 ms 565800 KB Output is correct
25 Correct 238 ms 565848 KB Output is correct
26 Correct 231 ms 565840 KB Output is correct
27 Correct 232 ms 565780 KB Output is correct
28 Correct 234 ms 565740 KB Output is correct
29 Correct 247 ms 565852 KB Output is correct
30 Correct 230 ms 565848 KB Output is correct
31 Correct 230 ms 565848 KB Output is correct
32 Correct 237 ms 565848 KB Output is correct
33 Correct 229 ms 565856 KB Output is correct
34 Correct 229 ms 565804 KB Output is correct
35 Correct 233 ms 565808 KB Output is correct
36 Correct 230 ms 565852 KB Output is correct
37 Correct 238 ms 565836 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 565716 KB Output is correct
2 Correct 236 ms 565788 KB Output is correct
3 Correct 223 ms 565800 KB Output is correct
4 Correct 225 ms 565748 KB Output is correct
5 Correct 227 ms 565708 KB Output is correct
6 Correct 230 ms 565708 KB Output is correct
7 Correct 221 ms 565812 KB Output is correct
8 Correct 233 ms 567748 KB Output is correct
9 Correct 221 ms 567756 KB Output is correct
10 Correct 222 ms 567884 KB Output is correct
11 Correct 242 ms 567740 KB Output is correct
12 Correct 221 ms 567948 KB Output is correct
13 Correct 232 ms 567808 KB Output is correct
14 Correct 234 ms 567700 KB Output is correct
15 Correct 231 ms 567832 KB Output is correct
16 Correct 225 ms 567812 KB Output is correct
17 Correct 243 ms 567844 KB Output is correct
18 Correct 226 ms 567796 KB Output is correct
19 Correct 234 ms 567836 KB Output is correct
20 Correct 232 ms 567816 KB Output is correct
21 Correct 236 ms 567896 KB Output is correct
22 Correct 228 ms 567800 KB Output is correct
23 Correct 236 ms 567756 KB Output is correct
24 Correct 226 ms 567712 KB Output is correct
25 Correct 240 ms 567824 KB Output is correct
26 Correct 244 ms 567756 KB Output is correct
27 Correct 228 ms 567712 KB Output is correct
28 Correct 238 ms 567756 KB Output is correct
29 Correct 231 ms 565812 KB Output is correct
30 Correct 231 ms 565780 KB Output is correct
31 Correct 229 ms 565724 KB Output is correct
32 Correct 233 ms 565684 KB Output is correct
33 Correct 234 ms 565792 KB Output is correct
34 Correct 228 ms 565676 KB Output is correct
35 Correct 234 ms 565796 KB Output is correct
36 Correct 226 ms 565708 KB Output is correct
37 Correct 251 ms 565768 KB Output is correct
38 Correct 226 ms 565708 KB Output is correct
39 Correct 234 ms 565776 KB Output is correct
40 Correct 249 ms 565784 KB Output is correct
41 Correct 232 ms 565788 KB Output is correct
42 Correct 234 ms 565788 KB Output is correct
43 Correct 235 ms 565860 KB Output is correct
44 Correct 231 ms 565796 KB Output is correct
45 Correct 233 ms 565848 KB Output is correct
46 Correct 241 ms 565824 KB Output is correct
47 Correct 230 ms 565812 KB Output is correct
48 Correct 234 ms 565836 KB Output is correct
49 Correct 227 ms 565844 KB Output is correct
50 Correct 243 ms 565852 KB Output is correct
51 Correct 232 ms 565832 KB Output is correct
52 Correct 233 ms 565800 KB Output is correct
53 Correct 238 ms 565848 KB Output is correct
54 Correct 231 ms 565840 KB Output is correct
55 Correct 232 ms 565780 KB Output is correct
56 Correct 234 ms 565740 KB Output is correct
57 Correct 247 ms 565852 KB Output is correct
58 Correct 230 ms 565848 KB Output is correct
59 Correct 230 ms 565848 KB Output is correct
60 Correct 237 ms 565848 KB Output is correct
61 Correct 229 ms 565856 KB Output is correct
62 Correct 229 ms 565804 KB Output is correct
63 Correct 233 ms 565808 KB Output is correct
64 Correct 230 ms 565852 KB Output is correct
65 Correct 238 ms 565836 KB Output is correct
66 Correct 244 ms 565964 KB Output is correct
67 Correct 235 ms 570188 KB Output is correct
68 Correct 238 ms 567984 KB Output is correct
69 Correct 228 ms 567988 KB Output is correct
70 Correct 241 ms 568344 KB Output is correct
71 Correct 231 ms 568140 KB Output is correct
72 Correct 240 ms 568116 KB Output is correct
73 Correct 236 ms 568008 KB Output is correct
74 Correct 233 ms 567924 KB Output is correct
75 Correct 228 ms 567964 KB Output is correct
76 Correct 237 ms 569784 KB Output is correct
77 Correct 242 ms 568728 KB Output is correct
78 Correct 233 ms 569548 KB Output is correct
79 Correct 250 ms 569396 KB Output is correct
80 Correct 246 ms 569420 KB Output is correct
81 Correct 224 ms 568268 KB Output is correct
82 Correct 226 ms 568924 KB Output is correct
83 Correct 262 ms 567960 KB Output is correct
84 Correct 237 ms 568224 KB Output is correct
85 Correct 234 ms 568008 KB Output is correct
86 Correct 251 ms 568276 KB Output is correct
87 Correct 235 ms 568316 KB Output is correct
88 Correct 234 ms 568376 KB Output is correct
89 Correct 251 ms 568128 KB Output is correct
90 Correct 235 ms 568020 KB Output is correct
91 Correct 234 ms 568072 KB Output is correct
92 Correct 237 ms 568400 KB Output is correct
93 Correct 262 ms 569744 KB Output is correct
94 Correct 241 ms 569808 KB Output is correct
95 Correct 279 ms 569168 KB Output is correct
96 Correct 231 ms 568516 KB Output is correct
97 Correct 380 ms 568112 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 565716 KB Output is correct
2 Correct 236 ms 565788 KB Output is correct
3 Correct 223 ms 565800 KB Output is correct
4 Correct 225 ms 565748 KB Output is correct
5 Correct 227 ms 565708 KB Output is correct
6 Correct 230 ms 565708 KB Output is correct
7 Correct 221 ms 565812 KB Output is correct
8 Correct 233 ms 567748 KB Output is correct
9 Correct 221 ms 567756 KB Output is correct
10 Correct 222 ms 567884 KB Output is correct
11 Correct 242 ms 567740 KB Output is correct
12 Correct 221 ms 567948 KB Output is correct
13 Correct 232 ms 567808 KB Output is correct
14 Correct 234 ms 567700 KB Output is correct
15 Correct 231 ms 567832 KB Output is correct
16 Correct 225 ms 567812 KB Output is correct
17 Correct 243 ms 567844 KB Output is correct
18 Correct 226 ms 567796 KB Output is correct
19 Correct 234 ms 567836 KB Output is correct
20 Correct 232 ms 567816 KB Output is correct
21 Correct 236 ms 567896 KB Output is correct
22 Correct 228 ms 567800 KB Output is correct
23 Correct 236 ms 567756 KB Output is correct
24 Correct 226 ms 567712 KB Output is correct
25 Correct 240 ms 567824 KB Output is correct
26 Correct 244 ms 567756 KB Output is correct
27 Correct 228 ms 567712 KB Output is correct
28 Correct 238 ms 567756 KB Output is correct
29 Correct 231 ms 565812 KB Output is correct
30 Correct 231 ms 565780 KB Output is correct
31 Correct 229 ms 565724 KB Output is correct
32 Correct 233 ms 565684 KB Output is correct
33 Correct 234 ms 565792 KB Output is correct
34 Correct 228 ms 565676 KB Output is correct
35 Correct 234 ms 565796 KB Output is correct
36 Correct 226 ms 565708 KB Output is correct
37 Correct 251 ms 565768 KB Output is correct
38 Correct 226 ms 565708 KB Output is correct
39 Correct 234 ms 565776 KB Output is correct
40 Correct 249 ms 565784 KB Output is correct
41 Correct 232 ms 565788 KB Output is correct
42 Correct 234 ms 565788 KB Output is correct
43 Correct 235 ms 565860 KB Output is correct
44 Correct 231 ms 565796 KB Output is correct
45 Correct 233 ms 565848 KB Output is correct
46 Correct 241 ms 565824 KB Output is correct
47 Correct 230 ms 565812 KB Output is correct
48 Correct 234 ms 565836 KB Output is correct
49 Correct 227 ms 565844 KB Output is correct
50 Correct 243 ms 565852 KB Output is correct
51 Correct 232 ms 565832 KB Output is correct
52 Correct 233 ms 565800 KB Output is correct
53 Correct 238 ms 565848 KB Output is correct
54 Correct 231 ms 565840 KB Output is correct
55 Correct 232 ms 565780 KB Output is correct
56 Correct 234 ms 565740 KB Output is correct
57 Correct 247 ms 565852 KB Output is correct
58 Correct 230 ms 565848 KB Output is correct
59 Correct 230 ms 565848 KB Output is correct
60 Correct 237 ms 565848 KB Output is correct
61 Correct 229 ms 565856 KB Output is correct
62 Correct 229 ms 565804 KB Output is correct
63 Correct 233 ms 565808 KB Output is correct
64 Correct 230 ms 565852 KB Output is correct
65 Correct 238 ms 565836 KB Output is correct
66 Correct 244 ms 565964 KB Output is correct
67 Correct 235 ms 570188 KB Output is correct
68 Correct 238 ms 567984 KB Output is correct
69 Correct 228 ms 567988 KB Output is correct
70 Correct 241 ms 568344 KB Output is correct
71 Correct 231 ms 568140 KB Output is correct
72 Correct 240 ms 568116 KB Output is correct
73 Correct 236 ms 568008 KB Output is correct
74 Correct 233 ms 567924 KB Output is correct
75 Correct 228 ms 567964 KB Output is correct
76 Correct 237 ms 569784 KB Output is correct
77 Correct 242 ms 568728 KB Output is correct
78 Correct 233 ms 569548 KB Output is correct
79 Correct 250 ms 569396 KB Output is correct
80 Correct 246 ms 569420 KB Output is correct
81 Correct 224 ms 568268 KB Output is correct
82 Correct 226 ms 568924 KB Output is correct
83 Correct 262 ms 567960 KB Output is correct
84 Correct 237 ms 568224 KB Output is correct
85 Correct 234 ms 568008 KB Output is correct
86 Correct 251 ms 568276 KB Output is correct
87 Correct 235 ms 568316 KB Output is correct
88 Correct 234 ms 568376 KB Output is correct
89 Correct 251 ms 568128 KB Output is correct
90 Correct 235 ms 568020 KB Output is correct
91 Correct 234 ms 568072 KB Output is correct
92 Correct 237 ms 568400 KB Output is correct
93 Correct 262 ms 569744 KB Output is correct
94 Correct 241 ms 569808 KB Output is correct
95 Correct 279 ms 569168 KB Output is correct
96 Correct 231 ms 568516 KB Output is correct
97 Correct 380 ms 568112 KB Output is correct
98 Correct 298 ms 610672 KB Output is correct
99 Correct 248 ms 569724 KB Output is correct
100 Correct 280 ms 595384 KB Output is correct
101 Correct 271 ms 588024 KB Output is correct
102 Correct 250 ms 580332 KB Output is correct
103 Correct 268 ms 584444 KB Output is correct
104 Correct 255 ms 580988 KB Output is correct
105 Correct 363 ms 590332 KB Output is correct
106 Correct 946 ms 593288 KB Output is correct
107 Correct 769 ms 612028 KB Output is correct
108 Correct 371 ms 604300 KB Output is correct
109 Correct 261 ms 582168 KB Output is correct
110 Correct 262 ms 580428 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 565716 KB Output is correct
2 Correct 236 ms 565788 KB Output is correct
3 Correct 223 ms 565800 KB Output is correct
4 Correct 225 ms 565748 KB Output is correct
5 Correct 227 ms 565708 KB Output is correct
6 Correct 230 ms 565708 KB Output is correct
7 Correct 221 ms 565812 KB Output is correct
8 Correct 233 ms 567748 KB Output is correct
9 Correct 221 ms 567756 KB Output is correct
10 Correct 222 ms 567884 KB Output is correct
11 Correct 242 ms 567740 KB Output is correct
12 Correct 221 ms 567948 KB Output is correct
13 Correct 232 ms 567808 KB Output is correct
14 Correct 234 ms 567700 KB Output is correct
15 Correct 231 ms 567832 KB Output is correct
16 Correct 225 ms 567812 KB Output is correct
17 Correct 243 ms 567844 KB Output is correct
18 Correct 226 ms 567796 KB Output is correct
19 Correct 234 ms 567836 KB Output is correct
20 Correct 232 ms 567816 KB Output is correct
21 Correct 236 ms 567896 KB Output is correct
22 Correct 228 ms 567800 KB Output is correct
23 Correct 236 ms 567756 KB Output is correct
24 Correct 226 ms 567712 KB Output is correct
25 Correct 240 ms 567824 KB Output is correct
26 Correct 244 ms 567756 KB Output is correct
27 Correct 228 ms 567712 KB Output is correct
28 Correct 238 ms 567756 KB Output is correct
29 Correct 230 ms 565752 KB Output is correct
30 Correct 240 ms 565708 KB Output is correct
31 Correct 237 ms 565908 KB Output is correct
32 Correct 238 ms 565816 KB Output is correct
33 Correct 232 ms 567844 KB Output is correct
34 Correct 230 ms 567756 KB Output is correct
35 Correct 230 ms 565828 KB Output is correct
36 Correct 232 ms 570296 KB Output is correct
37 Correct 267 ms 610596 KB Output is correct
38 Execution timed out 1139 ms 1048576 KB Time limit exceeded
39 Halted 0 ms 0 KB -