oj.uz

답안 #631299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631299 2022-08-18T02:57:39 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
5.55556 / 100
 1000 ms 262144 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 ll inf = 1e9;
const ld eps = 1e-6;
const int multitest = 0;
 
const int maxval = 1e7 + 10;
// const int maxval = 20;
 
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 (!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:114:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
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(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.55555555556 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 39412 KB Output is correct
2 Runtime error 729 ms 238592 KB Execution killed with signal 11
3 Correct 31 ms 41452 KB Output is correct
4 Runtime error 293 ms 238588 KB Execution killed with signal 11
5 Runtime error 451 ms 238444 KB Execution killed with signal 11
6 Correct 19 ms 39416 KB Output is correct
7 Correct 30 ms 41528 KB Output is correct
8 Correct 84 ms 46480 KB Output is correct
9 Runtime error 984 ms 238576 KB Execution killed with signal 11
10 Execution timed out 1062 ms 238456 KB Time limit exceeded
11 Runtime error 817 ms 238432 KB Execution killed with signal 11
12 Runtime error 277 ms 238536 KB Execution killed with signal 11
13 Execution timed out 1085 ms 95076 KB Time limit exceeded
14 Execution timed out 1094 ms 100504 KB Time limit exceeded
15 Runtime error 772 ms 238516 KB Execution killed with signal 11
16 Runtime error 750 ms 238504 KB Execution killed with signal 11
17 Runtime error 425 ms 238424 KB Execution killed with signal 11
18 Runtime error 270 ms 238488 KB Execution killed with signal 11

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 447 ms 246724 KB Execution killed with signal 11
2 Runtime error 441 ms 262144 KB Execution killed with signal 11
3 Execution timed out 1080 ms 100228 KB Time limit exceeded
4 Runtime error 541 ms 239688 KB Execution killed with signal 11
5 Execution timed out 1096 ms 124176 KB Time limit exceeded
6 Runtime error 605 ms 239264 KB Execution killed with signal 11
7 Runtime error 444 ms 246736 KB Execution killed with signal 11
8 Runtime error 505 ms 238868 KB Execution killed with signal 11
9 Execution timed out 1092 ms 114016 KB Time limit exceeded
10 Execution timed out 1091 ms 101436 KB Time limit exceeded
11 Execution timed out 1090 ms 98680 KB Time limit exceeded
12 Runtime error 887 ms 239204 KB Execution killed with signal 11
13 Runtime error 383 ms 241612 KB Execution killed with signal 11
14 Runtime error 563 ms 239800 KB Execution killed with signal 11
15 Execution timed out 1091 ms 102648 KB Time limit exceeded
16 Runtime error 413 ms 262144 KB Execution killed with signal 11
17 Execution timed out 1063 ms 102604 KB Time limit exceeded
18 Execution timed out 1054 ms 126448 KB Time limit exceeded

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1094 ms 101800 KB Time limit exceeded
2 Execution timed out 1101 ms 95600 KB Time limit exceeded
3 Execution timed out 1094 ms 93964 KB Time limit exceeded
4 Runtime error 980 ms 239784 KB Execution killed with signal 11
5 Runtime error 563 ms 262144 KB Execution killed with signal 11
6 Execution timed out 1090 ms 110560 KB Time limit exceeded
7 Execution timed out 1107 ms 222676 KB Time limit exceeded
8 Execution timed out 1052 ms 100928 KB Time limit exceeded
9 Execution timed out 1055 ms 95592 KB Time limit exceeded
10 Runtime error 930 ms 240180 KB Execution killed with signal 11
11 Runtime error 830 ms 239964 KB Execution killed with signal 11
12 Execution timed out 1079 ms 110756 KB Time limit exceeded
13 Execution timed out 1103 ms 103520 KB Time limit exceeded
14 Execution timed out 1032 ms 117680 KB Time limit exceeded
15 Execution timed out 1099 ms 102104 KB Time limit exceeded
16 Execution timed out 1093 ms 100116 KB Time limit exceeded
17 Execution timed out 1092 ms 108540 KB Time limit exceeded
18 Execution timed out 1075 ms 92776 KB Time limit exceeded
19 Runtime error 489 ms 243248 KB Execution killed with signal 11
20 Execution timed out 1092 ms 94724 KB Time limit exceeded
21 Execution timed out 1087 ms 115468 KB Time limit exceeded
22 Execution timed out 1087 ms 99412 KB Time limit exceeded
23 Runtime error 694 ms 250872 KB Execution killed with signal 11
24 Runtime error 375 ms 239368 KB Execution killed with signal 11
25 Execution timed out 1099 ms 131448 KB Time limit exceeded
26 Execution timed out 1091 ms 117036 KB Time limit exceeded
27 Execution timed out 1088 ms 91848 KB Time limit exceeded
28 Runtime error 540 ms 238828 KB Execution killed with signal 11
29 Execution timed out 1095 ms 107776 KB Time limit exceeded
30 Execution timed out 1103 ms 113284 KB Time limit exceeded
31 Runtime error 542 ms 241096 KB Execution killed with signal 11
32 Runtime error 609 ms 239576 KB Execution killed with signal 11
33 Runtime error 315 ms 239776 KB Execution killed with signal 11
34 Execution timed out 1098 ms 146932 KB Time limit exceeded
35 Runtime error 507 ms 240188 KB Execution killed with signal 11
36 Execution timed out 1067 ms 98756 KB Time limit exceeded
37 Runtime error 551 ms 262144 KB Execution killed with signal 11
38 Execution timed out 1089 ms 101400 KB Time limit exceeded
39 Runtime error 488 ms 239768 KB Execution killed with signal 11
40 Execution timed out 1089 ms 115512 KB Time limit exceeded
41 Execution timed out 1105 ms 174200 KB Time limit exceeded
42 Execution timed out 1100 ms 100036 KB Time limit exceeded