답안 #631289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631289	2022-08-18T02:44:29 Z	mousey	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	7.77778 / 100	1000 ms	78580 KB

brunhilda

#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define pdb pair <double, double> 
#define YES cout<<"YES"
#define NO cout<<"NO"
#define endl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll> 
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;

const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const ll N=1e5, MAXN=1e7;
ll n, q;
ll a[N+5];
ll ans[MAXN+5];
ll product=1;

void input()
{
	cin >> n >> q;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		product*=a[i];
		if(product>=MAXN) product=MAXN;
	}
}

void solve()
{
	for(int i = 1; i <= MAXN; i++)
	{
		ans[i]=INFINF;
		if(i>=product) continue;
		for(int j = n; j >= 1; j--)
		{
			if(i%a[j])
			{
				ans[i]=min(ans[i], ans[i-i%a[j]]+1);
			}
		}
	}
	while(q--)
	{
		ll x;
		cin >> x;
		if(ans[x]==INFINF) cout << "oo";
		else cout << ans[x];
		endl;
	}
}

int main() 
{
//	auto start_time = chrono::high_resolution_clock::now();
//	freopen("test.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
    input();
    solve();
//    auto end_time = chrono::high_resolution_clock::now();
//        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
//        cout << "\n[ " << duration << " ms ]\n"; 
}

Subtask #1
7.77777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	78564 KB	Output is correct
2	Execution timed out	1093 ms	27820 KB	Time limit exceeded
3	Correct	44 ms	78580 KB	Output is correct
4	Execution timed out	1071 ms	16048 KB	Time limit exceeded
5	Correct	852 ms	78548 KB	Output is correct
6	Correct	48 ms	78540 KB	Output is correct
7	Correct	44 ms	78500 KB	Output is correct
8	Correct	75 ms	78520 KB	Output is correct
9	Correct	955 ms	78552 KB	Output is correct
10	Execution timed out	1046 ms	43448 KB	Time limit exceeded
11	Execution timed out	1077 ms	38384 KB	Time limit exceeded
12	Execution timed out	1089 ms	12760 KB	Time limit exceeded
13	Execution timed out	1083 ms	1580 KB	Time limit exceeded
14	Execution timed out	1094 ms	1732 KB	Time limit exceeded
15	Execution timed out	1049 ms	32668 KB	Time limit exceeded
16	Execution timed out	1063 ms	26692 KB	Time limit exceeded
17	Execution timed out	1099 ms	15260 KB	Time limit exceeded
18	Execution timed out	1099 ms	16572 KB	Time limit exceeded

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1074 ms	536 KB	Time limit exceeded
2	Execution timed out	1087 ms	1036 KB	Time limit exceeded
3	Execution timed out	1088 ms	1004 KB	Time limit exceeded
4	Execution timed out	1096 ms	776 KB	Time limit exceeded
5	Execution timed out	1057 ms	740 KB	Time limit exceeded
6	Execution timed out	1060 ms	1516 KB	Time limit exceeded
7	Execution timed out	1061 ms	628 KB	Time limit exceeded
8	Execution timed out	1086 ms	1784 KB	Time limit exceeded
9	Execution timed out	1072 ms	1004 KB	Time limit exceeded
10	Execution timed out	1092 ms	884 KB	Time limit exceeded
11	Execution timed out	1083 ms	664 KB	Time limit exceeded
12	Execution timed out	1075 ms	1124 KB	Time limit exceeded
13	Execution timed out	1092 ms	888 KB	Time limit exceeded
14	Execution timed out	1045 ms	820 KB	Time limit exceeded
15	Execution timed out	1078 ms	676 KB	Time limit exceeded
16	Execution timed out	1078 ms	1100 KB	Time limit exceeded
17	Execution timed out	1085 ms	840 KB	Time limit exceeded
18	Execution timed out	1087 ms	1220 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1042 ms	724 KB	Time limit exceeded
2	Execution timed out	1086 ms	856 KB	Time limit exceeded
3	Execution timed out	1086 ms	724 KB	Time limit exceeded
4	Execution timed out	1050 ms	888 KB	Time limit exceeded
5	Execution timed out	1031 ms	1108 KB	Time limit exceeded
6	Execution timed out	1071 ms	480 KB	Time limit exceeded
7	Execution timed out	1055 ms	1100 KB	Time limit exceeded
8	Execution timed out	1079 ms	708 KB	Time limit exceeded
9	Execution timed out	1099 ms	724 KB	Time limit exceeded
10	Execution timed out	1089 ms	428 KB	Time limit exceeded
11	Execution timed out	1082 ms	892 KB	Time limit exceeded
12	Execution timed out	1092 ms	660 KB	Time limit exceeded
13	Execution timed out	1085 ms	604 KB	Time limit exceeded
14	Execution timed out	1091 ms	35700 KB	Time limit exceeded
15	Execution timed out	1085 ms	732 KB	Time limit exceeded
16	Execution timed out	1080 ms	608 KB	Time limit exceeded
17	Execution timed out	1089 ms	808 KB	Time limit exceeded
18	Execution timed out	1076 ms	748 KB	Time limit exceeded
19	Execution timed out	1094 ms	684 KB	Time limit exceeded
20	Execution timed out	1093 ms	728 KB	Time limit exceeded
21	Execution timed out	1069 ms	12400 KB	Time limit exceeded
22	Execution timed out	1087 ms	1108 KB	Time limit exceeded
23	Execution timed out	1083 ms	700 KB	Time limit exceeded
24	Execution timed out	1079 ms	1748 KB	Time limit exceeded
25	Execution timed out	1083 ms	928 KB	Time limit exceeded
26	Execution timed out	1078 ms	880 KB	Time limit exceeded
27	Execution timed out	1090 ms	1220 KB	Time limit exceeded
28	Execution timed out	1097 ms	2000 KB	Time limit exceeded
29	Execution timed out	1091 ms	1100 KB	Time limit exceeded
30	Execution timed out	1085 ms	992 KB	Time limit exceeded
31	Execution timed out	1081 ms	904 KB	Time limit exceeded
32	Execution timed out	1088 ms	1108 KB	Time limit exceeded
33	Execution timed out	1078 ms	1700 KB	Time limit exceeded
34	Execution timed out	1098 ms	1100 KB	Time limit exceeded
35	Execution timed out	1096 ms	1156 KB	Time limit exceeded
36	Execution timed out	1086 ms	1036 KB	Time limit exceeded
37	Execution timed out	1080 ms	1096 KB	Time limit exceeded
38	Execution timed out	1078 ms	608 KB	Time limit exceeded
39	Execution timed out	1092 ms	1180 KB	Time limit exceeded
40	Execution timed out	1076 ms	664 KB	Time limit exceeded
41	Execution timed out	1088 ms	1108 KB	Time limit exceeded
42	Execution timed out	1090 ms	848 KB	Time limit exceeded

답안 #631289

Compilation message

Subtask #1 7.77777777778 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
7.77777777778 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0