oj.uz

Submission #283155

# Submission time Handle Problem Language Result Execution time Memory
283155 2020-08-25T10:40:52 Z theStaticMind Brunhilda’s Birthday (BOI13_brunhilda) C++14
48.4127 / 100
 1000 ms 40312 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;

int dp[10000001];

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int m, q;
	cin >> m >> q;

	vector<int> P(m);
	for(int i = 0; i < m; i++) cin >> P[i];

	for(int i = 1; i <= 1e7; i++){
		dp[i] = 1e9;
		for(int j = m - 1; j >= 0 && j >= m - 12; j--){
			dp[i] = min(dp[i], dp[i - i % P[j]] + 1);

		}
	}

	while(q--){
		int n;
		cin >> n;

		if(dp[n] >= 1e9) cout << "oo\n";
		else cout << dp[n] << "\n";
	}
}

Subtask #1
14.4444444444 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 39416 KB Output is correct
2 Correct 944 ms 39488 KB Output is correct
3 Correct 452 ms 39604 KB Output is correct
4 Incorrect 881 ms 39544 KB Output isn't correct
5 Correct 853 ms 39616 KB Output is correct
6 Correct 285 ms 39416 KB Output is correct
7 Correct 454 ms 39544 KB Output is correct
8 Correct 542 ms 39440 KB Output is correct
9 Correct 882 ms 39416 KB Output is correct
10 Correct 1000 ms 39512 KB Output is correct
11 Execution timed out 1041 ms 39544 KB Time limit exceeded
12 Correct 892 ms 39412 KB Output is correct
13 Correct 848 ms 39404 KB Output is correct
14 Correct 871 ms 39544 KB Output is correct
15 Correct 974 ms 39404 KB Output is correct
16 Execution timed out 1004 ms 39468 KB Time limit exceeded
17 Incorrect 959 ms 39512 KB Output isn't correct
18 Incorrect 887 ms 39504 KB Output isn't correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 39688 KB Output is correct
2 Correct 670 ms 39928 KB Output is correct
3 Correct 697 ms 39792 KB Output is correct
4 Incorrect 767 ms 39488 KB Output isn't correct
5 Correct 689 ms 39800 KB Output is correct
6 Incorrect 769 ms 39544 KB Output isn't correct
7 Correct 695 ms 39544 KB Output is correct
8 Incorrect 819 ms 39672 KB Output isn't correct
9 Correct 720 ms 39928 KB Output is correct
10 Correct 702 ms 39800 KB Output is correct
11 Incorrect 728 ms 39672 KB Output isn't correct
12 Incorrect 782 ms 39436 KB Output isn't correct
13 Incorrect 730 ms 39488 KB Output isn't correct
14 Incorrect 778 ms 39544 KB Output isn't correct
15 Correct 705 ms 39800 KB Output is correct
16 Correct 670 ms 39932 KB Output is correct
17 Correct 804 ms 39672 KB Output is correct
18 Incorrect 685 ms 39928 KB Output isn't correct

Subtask #3
22.8571428571 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 39800 KB Output is correct
2 Incorrect 729 ms 39812 KB Output isn't correct
3 Correct 710 ms 39800 KB Output is correct
4 Incorrect 793 ms 39712 KB Output isn't correct
5 Correct 690 ms 40092 KB Output is correct
6 Incorrect 795 ms 39836 KB Output isn't correct
7 Correct 691 ms 40020 KB Output is correct
8 Correct 722 ms 39756 KB Output is correct
9 Correct 715 ms 39872 KB Output is correct
10 Incorrect 769 ms 39544 KB Output isn't correct
11 Incorrect 766 ms 39544 KB Output isn't correct
12 Incorrect 765 ms 39612 KB Output isn't correct
13 Incorrect 747 ms 39884 KB Output isn't correct
14 Execution timed out 1024 ms 40136 KB Time limit exceeded
15 Incorrect 792 ms 39548 KB Output isn't correct
16 Incorrect 796 ms 39584 KB Output isn't correct
17 Incorrect 711 ms 39700 KB Output isn't correct
18 Incorrect 706 ms 39672 KB Output isn't correct
19 Incorrect 711 ms 39652 KB Output isn't correct
20 Correct 723 ms 39856 KB Output is correct
21 Incorrect 998 ms 40128 KB Output isn't correct
22 Correct 718 ms 40040 KB Output is correct
23 Correct 740 ms 39820 KB Output is correct
24 Incorrect 789 ms 39928 KB Output isn't correct
25 Incorrect 816 ms 39856 KB Output isn't correct
26 Incorrect 786 ms 39928 KB Output isn't correct
27 Correct 696 ms 40056 KB Output is correct
28 Incorrect 777 ms 39844 KB Output isn't correct
29 Correct 722 ms 40136 KB Output is correct
30 Correct 746 ms 40200 KB Output is correct
31 Incorrect 767 ms 39852 KB Output isn't correct
32 Incorrect 796 ms 39736 KB Output isn't correct
33 Incorrect 769 ms 39804 KB Output isn't correct
34 Correct 692 ms 39928 KB Output is correct
35 Incorrect 783 ms 39728 KB Output isn't correct
36 Correct 734 ms 40032 KB Output is correct
37 Correct 684 ms 40312 KB Output is correct
38 Incorrect 803 ms 39928 KB Output isn't correct
39 Incorrect 806 ms 39764 KB Output isn't correct
40 Incorrect 794 ms 39704 KB Output isn't correct
41 Correct 707 ms 40000 KB Output is correct
42 Incorrect 852 ms 40028 KB Output isn't correct