oj.uz

Submission #837763

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -