oj.uz

Submission #631308

# Submission time Handle Problem Language Result Execution time Memory
631308 2022-08-18T03:04:30 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
50.3175 / 100
 1000 ms 160688 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;
	}
 
	queue<int> q;
	dp[0] = 0; q.push(0);
 
	int lim = 1;
 
	while (!q.empty()){
		int x = q.front(); q.pop();
 
		if (divs[x]){
			for (auto i: *divs[x]){
				while (lim < min(x + i, maxval)){
					dp[lim] = dp[x] + 1; q.push(lim);
					lim++;
				}
				if (x + i < maxval){
					if (!divs[x + i]) divs[x + i] = new vector<int>;
					divs[x + i]->push_back(i);
				}
			}
			delete divs[x];
		}
	}
 
	for (int i = 0; i < Q; i++){
		int x; cin >> x;
		if (dp[x] == inf) cout << "oo\n";
		else cout << dp[x] << "\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:115:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:116:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39508 KB Output is correct
2 Correct 583 ms 117676 KB Output is correct
3 Correct 31 ms 41420 KB Output is correct
4 Correct 169 ms 117724 KB Output is correct
5 Correct 287 ms 117624 KB Output is correct
6 Correct 18 ms 39472 KB Output is correct
7 Correct 31 ms 41400 KB Output is correct
8 Correct 74 ms 46504 KB Output is correct
9 Correct 810 ms 117628 KB Output is correct
10 Correct 871 ms 117668 KB Output is correct
11 Correct 651 ms 117684 KB Output is correct
12 Correct 146 ms 117616 KB Output is correct
13 Execution timed out 1097 ms 102060 KB Time limit exceeded
14 Execution timed out 1099 ms 108616 KB Time limit exceeded
15 Correct 581 ms 117812 KB Output is correct
16 Correct 584 ms 117708 KB Output is correct
17 Correct 287 ms 117732 KB Output is correct
18 Correct 164 ms 117720 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 122352 KB Output is correct
2 Correct 436 ms 160688 KB Output is correct
3 Execution timed out 1094 ms 102864 KB Time limit exceeded
4 Correct 406 ms 118396 KB Output is correct
5 Execution timed out 1096 ms 126572 KB Time limit exceeded
6 Correct 482 ms 118080 KB Output is correct
7 Correct 329 ms 122224 KB Output is correct
8 Correct 386 ms 117916 KB Output is correct
9 Execution timed out 1096 ms 116424 KB Time limit exceeded
10 Execution timed out 1098 ms 101676 KB Time limit exceeded
11 Execution timed out 1100 ms 99376 KB Time limit exceeded
12 Correct 751 ms 118048 KB Output is correct
13 Correct 299 ms 119980 KB Output is correct
14 Correct 403 ms 118344 KB Output is correct
15 Execution timed out 1085 ms 105416 KB Time limit exceeded
16 Correct 426 ms 160688 KB Output is correct
17 Execution timed out 1102 ms 104900 KB Time limit exceeded
18 Execution timed out 1104 ms 129396 KB Time limit exceeded

Subtask #3
21.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 98928 KB Time limit exceeded
2 Execution timed out 1079 ms 92804 KB Time limit exceeded
3 Execution timed out 1093 ms 93116 KB Time limit exceeded
4 Correct 940 ms 118636 KB Output is correct
5 Correct 591 ms 142772 KB Output is correct
6 Execution timed out 1078 ms 107080 KB Time limit exceeded
7 Execution timed out 1099 ms 136020 KB Time limit exceeded
8 Execution timed out 1062 ms 100960 KB Time limit exceeded
9 Execution timed out 1098 ms 102012 KB Time limit exceeded
10 Correct 835 ms 118568 KB Output is correct
11 Correct 648 ms 118396 KB Output is correct
12 Execution timed out 1085 ms 112448 KB Time limit exceeded
13 Execution timed out 1082 ms 98672 KB Time limit exceeded
14 Correct 970 ms 118204 KB Output is correct
15 Execution timed out 1087 ms 101604 KB Time limit exceeded
16 Execution timed out 1098 ms 99324 KB Time limit exceeded
17 Execution timed out 1069 ms 100276 KB Time limit exceeded
18 Execution timed out 1026 ms 84552 KB Time limit exceeded
19 Correct 439 ms 121032 KB Output is correct
20 Execution timed out 1091 ms 90736 KB Time limit exceeded
21 Execution timed out 1085 ms 110988 KB Time limit exceeded
22 Execution timed out 1083 ms 95892 KB Time limit exceeded
23 Correct 592 ms 124108 KB Output is correct
24 Correct 293 ms 118476 KB Output is correct
25 Execution timed out 1052 ms 118456 KB Time limit exceeded
26 Execution timed out 1060 ms 118600 KB Time limit exceeded
27 Execution timed out 1078 ms 93488 KB Time limit exceeded
28 Correct 385 ms 118864 KB Output is correct
29 Execution timed out 1084 ms 102676 KB Time limit exceeded
30 Execution timed out 1104 ms 103892 KB Time limit exceeded
31 Correct 496 ms 119488 KB Output is correct
32 Correct 604 ms 118524 KB Output is correct
33 Correct 290 ms 118836 KB Output is correct
34 Execution timed out 1091 ms 133348 KB Time limit exceeded
35 Correct 461 ms 118864 KB Output is correct
36 Execution timed out 1090 ms 101496 KB Time limit exceeded
37 Correct 615 ms 142764 KB Output is correct
38 Execution timed out 1097 ms 98588 KB Time limit exceeded
39 Correct 344 ms 118656 KB Output is correct
40 Execution timed out 1099 ms 104972 KB Time limit exceeded
41 Execution timed out 1097 ms 154684 KB Time limit exceeded
42 Execution timed out 1090 ms 96760 KB Time limit exceeded