oj.uz

Submission #631316

# Submission time Handle Problem Language Result Execution time Memory
631316 2022-08-18T03:11:26 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
55.7143 / 100
 1000 ms 124528 KB 
/*
	Unknown's C++ Template (v3.2)
*/
 
#include "bits/stdc++.h"
using namespace std;
 
// #define int long long
 
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
 
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mid ((l+r)>>1)
#define fi first
#define se second
 
#ifdef LOCAL
	#define debug(x) cout << #x << " = " << x << "\n";
#else
	#define debug(x) ;
#endif
 
template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x)
{ out << "(" << x.first << ", " << x.second << ")"; return out; }
 
template <class T>
ostream& operator << (ostream& out, vector<T> x){
	out << "[";
	for (int i=0; i<sz(x); i++) { out << (i ? ", " : "") << x[i]; }
	out << "]"; return out;
}
 
template <class T>
istream& operator >> (istream& in, vector<T> &x){
	for (auto &i: x) in >> i;
	return in;
}
 
const ld PI = acos(-1.0);
const int allmod[3] = {(int)1e9+7, 998244353, (int)1e9+9};
const int mod = allmod[0];
const int maxn = 2e5 + 64;
const int inf = 1e9;
const ld eps = 1e-6;
const int multitest = 0;
 
const int maxval = 1e7 + 10;
 
int dp[maxval];
vector<int> *divs[maxval];
 
void main_program(){
	int m, Q; cin >> m >> Q;
	vi v(m); cin >> v; sort(all(v));
 
	divs[0] = new vector<int>;
	for (int i = 0; i < m; i++) divs[0]->push_back(v[i]);
 
	for (int i = 0; i < maxval; i++){
		dp[i] = inf;
	}
 
	dp[0] = 0;
 
	int x = 0, lim = 1;
	while (x < lim && lim < maxval){
		if (divs[x]){
			for (auto i: *divs[x]){
				while (lim < min(x + i, maxval)){
					dp[lim] = dp[x] + 1;
					lim++;
				}
				if (x + i < maxval){
					if (!divs[x + i]) divs[x + i] = new vector<int>;
					divs[x + i]->push_back(i);
				}
			}
			delete divs[x];
		}
		x++;
	}
 
	for (int i = 0; i < Q; i++){
		int a; cin >> a;
		if (dp[a] == inf) cout << "oo\n";
		else cout << dp[a] << "\n";
	}
}
 
void pre_main(){
 
}
 
signed main(){
	#ifdef LOCAL
		auto stime = chrono::high_resolution_clock::now();
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#ifndef ONLINE_JUDGE
		if (fopen(".inp", "r")){
			freopen(".inp", "r", stdin);
			freopen(".out", "w", stdout);
		}
	#endif
	int t = 1; if (multitest) cin >> t;
	pre_main();
	while (t--) main_program();
	#ifdef LOCAL
		auto etime = chrono::high_resolution_clock::now();
		auto duration = chrono::duration_cast<chrono::milliseconds>(etime-stime).count();
		cout << "\n[" << duration << "ms]\n";
	#endif
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:112:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:113:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 39460 KB Output is correct
2 Correct 862 ms 117692 KB Output is correct
3 Correct 33 ms 41428 KB Output is correct
4 Correct 138 ms 117636 KB Output is correct
5 Correct 241 ms 117716 KB Output is correct
6 Correct 22 ms 39428 KB Output is correct
7 Correct 33 ms 41496 KB Output is correct
8 Correct 77 ms 46528 KB Output is correct
9 Correct 770 ms 117684 KB Output is correct
10 Correct 885 ms 117872 KB Output is correct
11 Correct 643 ms 117720 KB Output is correct
12 Correct 122 ms 117700 KB Output is correct
13 Execution timed out 1102 ms 111204 KB Time limit exceeded
14 Execution timed out 1087 ms 100960 KB Time limit exceeded
15 Correct 582 ms 117712 KB Output is correct
16 Correct 666 ms 117676 KB Output is correct
17 Correct 252 ms 117656 KB Output is correct
18 Correct 240 ms 117656 KB Output is correct

Subtask #2
12.2222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 117980 KB Output is correct
2 Correct 391 ms 123192 KB Output is correct
3 Execution timed out 1085 ms 92356 KB Time limit exceeded
4 Correct 382 ms 117868 KB Output is correct
5 Correct 957 ms 121108 KB Output is correct
6 Correct 429 ms 117712 KB Output is correct
7 Correct 270 ms 117912 KB Output is correct
8 Correct 347 ms 117700 KB Output is correct
9 Execution timed out 1088 ms 110116 KB Time limit exceeded
10 Execution timed out 1095 ms 97340 KB Time limit exceeded
11 Execution timed out 1097 ms 103132 KB Time limit exceeded
12 Correct 745 ms 117768 KB Output is correct
13 Correct 262 ms 117096 KB Output is correct
14 Correct 366 ms 117980 KB Output is correct
15 Execution timed out 1031 ms 107060 KB Time limit exceeded
16 Correct 214 ms 123108 KB Output is correct
17 Execution timed out 1107 ms 113044 KB Time limit exceeded
18 Execution timed out 1081 ms 118700 KB Time limit exceeded

Subtask #3
25.7142857143 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 105276 KB Time limit exceeded
2 Execution timed out 1094 ms 95272 KB Time limit exceeded
3 Execution timed out 1100 ms 99004 KB Time limit exceeded
4 Correct 932 ms 118144 KB Output is correct
5 Correct 338 ms 124360 KB Output is correct
6 Execution timed out 1106 ms 109368 KB Time limit exceeded
7 Execution timed out 1022 ms 124528 KB Time limit exceeded
8 Execution timed out 1095 ms 106568 KB Time limit exceeded
9 Execution timed out 1094 ms 95924 KB Time limit exceeded
10 Correct 748 ms 118048 KB Output is correct
11 Correct 580 ms 118032 KB Output is correct
12 Execution timed out 1068 ms 118124 KB Time limit exceeded
13 Execution timed out 1090 ms 97888 KB Time limit exceeded
14 Correct 939 ms 118248 KB Output is correct
15 Execution timed out 1098 ms 111308 KB Time limit exceeded
16 Execution timed out 1098 ms 108196 KB Time limit exceeded
17 Execution timed out 1098 ms 118344 KB Time limit exceeded
18 Execution timed out 1098 ms 99712 KB Time limit exceeded
19 Correct 351 ms 117068 KB Output is correct
20 Execution timed out 1095 ms 99664 KB Time limit exceeded
21 Execution timed out 1025 ms 118276 KB Time limit exceeded
22 Execution timed out 1096 ms 100016 KB Time limit exceeded
23 Correct 448 ms 119912 KB Output is correct
24 Correct 237 ms 117916 KB Output is correct
25 Correct 854 ms 118220 KB Output is correct
26 Correct 833 ms 118180 KB Output is correct
27 Execution timed out 1085 ms 96932 KB Time limit exceeded
28 Correct 300 ms 117288 KB Output is correct
29 Execution timed out 1100 ms 114496 KB Time limit exceeded
30 Execution timed out 1085 ms 122280 KB Time limit exceeded
31 Correct 454 ms 117952 KB Output is correct
32 Correct 469 ms 118192 KB Output is correct
33 Correct 183 ms 117680 KB Output is correct
34 Execution timed out 1093 ms 124416 KB Time limit exceeded
35 Correct 376 ms 118088 KB Output is correct
36 Execution timed out 1088 ms 97312 KB Time limit exceeded
37 Correct 397 ms 124432 KB Output is correct
38 Execution timed out 1099 ms 113920 KB Time limit exceeded
39 Correct 276 ms 118004 KB Output is correct
40 Execution timed out 1028 ms 118512 KB Time limit exceeded
41 Correct 777 ms 123644 KB Output is correct
42 Execution timed out 1092 ms 108720 KB Time limit exceeded