oj.uz

답안 #631297

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631297 2022-08-18T02:55:37 Z mousey Brunhilda’s Birthday (BOI13_brunhilda) C++14
48.0952 / 100
 866 ms 79632 KB 
#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()
{
	ll cur=n;
	for(int i = 2; i <= MAXN; i++)
	{
		ans[i]=INFINF;
		if(i>=product) continue;
		if(i<a[n])
		{
			ans[i]=1;
			continue;
		}
		for(int j = n; j >= 1 && j >= n-8; j--)
		{
			if(i%a[j]) ans[i]=min(ans[i], ans[i-i%a[j]]+1);
		}
		for(int j = n-9; j >= 1; j--)
		{
			if(i%a[j])
			{
				ans[i]=min(ans[i], ans[i-i%a[j]]+1);
				break;
			}
		}
	}
	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"; 
}

Compilation message

brunhilda.cpp: In function 'void solve()':
brunhilda.cpp:41:5: warning: unused variable 'cur' [-Wunused-variable]
   41 |  ll cur=n;
      |     ^~~

Subtask #1
15.5555555556 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 78540 KB Output is correct
2 Correct 718 ms 78504 KB Output is correct
3 Correct 45 ms 78468 KB Output is correct
4 Incorrect 653 ms 78544 KB Output isn't correct
5 Correct 778 ms 78544 KB Output is correct
6 Correct 33 ms 78540 KB Output is correct
7 Correct 50 ms 78560 KB Output is correct
8 Correct 76 ms 78492 KB Output is correct
9 Correct 866 ms 78640 KB Output is correct
10 Correct 758 ms 78524 KB Output is correct
11 Correct 760 ms 78656 KB Output is correct
12 Correct 639 ms 78540 KB Output is correct
13 Correct 619 ms 78476 KB Output is correct
14 Incorrect 632 ms 78700 KB Output isn't correct
15 Correct 714 ms 78536 KB Output is correct
16 Correct 715 ms 78584 KB Output is correct
17 Incorrect 725 ms 78676 KB Output isn't correct
18 Incorrect 648 ms 78604 KB Output isn't correct

Subtask #2
11.1111111111 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 489 ms 78668 KB Output is correct
2 Correct 87 ms 79284 KB Output is correct
3 Correct 438 ms 79136 KB Output is correct
4 Incorrect 565 ms 78692 KB Output isn't correct
5 Correct 477 ms 79052 KB Output is correct
6 Incorrect 579 ms 78616 KB Output isn't correct
7 Correct 469 ms 78576 KB Output is correct
8 Incorrect 614 ms 78580 KB Output isn't correct
9 Correct 471 ms 79136 KB Output is correct
10 Correct 411 ms 79104 KB Output is correct
11 Incorrect 512 ms 78904 KB Output isn't correct
12 Incorrect 596 ms 78632 KB Output isn't correct
13 Incorrect 534 ms 78696 KB Output isn't correct
14 Incorrect 586 ms 78580 KB Output isn't correct
15 Correct 508 ms 78832 KB Output is correct
16 Correct 91 ms 79208 KB Output is correct
17 Correct 597 ms 78748 KB Output is correct
18 Incorrect 300 ms 79304 KB Output isn't correct

Subtask #3
21.4285714286 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 499 ms 79020 KB Output is correct
2 Incorrect 500 ms 79068 KB Output isn't correct
3 Correct 498 ms 79144 KB Output is correct
4 Incorrect 588 ms 78796 KB Output isn't correct
5 Correct 376 ms 79632 KB Output is correct
6 Incorrect 582 ms 78940 KB Output isn't correct
7 Correct 390 ms 79444 KB Output is correct
8 Correct 493 ms 79104 KB Output is correct
9 Correct 495 ms 79020 KB Output is correct
10 Incorrect 579 ms 78568 KB Output isn't correct
11 Incorrect 564 ms 78588 KB Output isn't correct
12 Incorrect 594 ms 78680 KB Output isn't correct
13 Incorrect 529 ms 79184 KB Output isn't correct
14 Incorrect 757 ms 79224 KB Output isn't correct
15 Incorrect 588 ms 78672 KB Output isn't correct
16 Incorrect 578 ms 78668 KB Output isn't correct
17 Incorrect 494 ms 78956 KB Output isn't correct
18 Incorrect 516 ms 79124 KB Output isn't correct
19 Incorrect 504 ms 78588 KB Output isn't correct
20 Correct 483 ms 79112 KB Output is correct
21 Incorrect 706 ms 79192 KB Output isn't correct
22 Correct 478 ms 79544 KB Output is correct
23 Incorrect 521 ms 78940 KB Output isn't correct
24 Incorrect 604 ms 78788 KB Output isn't correct
25 Incorrect 609 ms 78920 KB Output isn't correct
26 Incorrect 588 ms 78952 KB Output isn't correct
27 Correct 447 ms 79456 KB Output is correct
28 Incorrect 581 ms 78848 KB Output isn't correct
29 Correct 499 ms 79600 KB Output is correct
30 Correct 503 ms 79276 KB Output is correct
31 Incorrect 542 ms 78856 KB Output isn't correct
32 Incorrect 594 ms 78816 KB Output isn't correct
33 Incorrect 588 ms 78816 KB Output isn't correct
34 Correct 372 ms 79516 KB Output is correct
35 Incorrect 594 ms 79196 KB Output isn't correct
36 Correct 469 ms 79432 KB Output is correct
37 Correct 344 ms 79488 KB Output is correct
38 Incorrect 603 ms 78804 KB Output isn't correct
39 Incorrect 591 ms 78844 KB Output isn't correct
40 Incorrect 575 ms 78884 KB Output isn't correct
41 Correct 179 ms 79440 KB Output is correct
42 Incorrect 629 ms 78940 KB Output isn't correct