Submission #283228

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
283228	2020-08-25T11:41:59 Z	Atill83	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	49.2063 / 100	995 ms	40568 KB

brunhilda

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 1e7+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll m, q;
ll p[(int)1e5 + 5];
int ans[MAXN];



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>m>>q;
    memset(ans, 0x7f, sizeof(ans));
    for(int i = 0; i < m; i++){
        cin>>p[i];
    }

    for(int i = 1; i < p[m - 1]; i++){
        ans[i] = 1;
    }

    for(int i = p[m - 1]; i <= 1e7; i++){
        //int mnI = -1;
        for(int j = m - 1; j >= max(m - 10, 0LL); j--){
            if(i % p[j] == 0) continue;
            if(ans[i - i % p[j]] + 1 < ans[i]){
                ans[i] = ans[i - i % p[j]] + 1;
                //mnI = j;
            }
        }
        //cout<<ans[i]<<" "<<mnI<<endl;
    }

    for(int i = 0; i < q; i++){
        int n;
        cin>>n;
        if(ans[n] > 1e7){
            cout<<"oo"<<endl;
        }else{
            cout<<ans[n]<<endl;
        }
    }

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1

16.6666666667 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	296 ms	39544 KB	Output is correct
2	Correct	789 ms	39544 KB	Output is correct
3	Correct	485 ms	39424 KB	Output is correct
4	Incorrect	735 ms	39544 KB	Output isn't correct
5	Correct	879 ms	39544 KB	Output is correct
6	Correct	299 ms	39544 KB	Output is correct
7	Correct	483 ms	39544 KB	Output is correct
8	Correct	571 ms	39544 KB	Output is correct
9	Correct	995 ms	39544 KB	Output is correct
10	Correct	855 ms	39532 KB	Output is correct
11	Correct	843 ms	39532 KB	Output is correct
12	Correct	731 ms	39544 KB	Output is correct
13	Correct	695 ms	39424 KB	Output is correct
14	Correct	700 ms	39544 KB	Output is correct
15	Correct	794 ms	39544 KB	Output is correct
16	Correct	793 ms	39532 KB	Output is correct
17	Incorrect	794 ms	39528 KB	Output isn't correct
18	Incorrect	736 ms	39544 KB	Output isn't correct

Subtask #2

11.1111111111 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	544 ms	39552 KB	Output is correct
2	Correct	90 ms	40184 KB	Output is correct
3	Correct	458 ms	40184 KB	Output is correct
4	Incorrect	641 ms	39672 KB	Output isn't correct
5	Correct	513 ms	39928 KB	Output is correct
6	Incorrect	639 ms	39424 KB	Output isn't correct
7	Correct	542 ms	39628 KB	Output is correct
8	Incorrect	677 ms	39544 KB	Output isn't correct
9	Correct	509 ms	40188 KB	Output is correct
10	Correct	458 ms	40184 KB	Output is correct
11	Incorrect	558 ms	39928 KB	Output isn't correct
12	Incorrect	653 ms	39680 KB	Output isn't correct
13	Incorrect	575 ms	39552 KB	Output isn't correct
14	Incorrect	641 ms	39672 KB	Output isn't correct
15	Correct	553 ms	39928 KB	Output is correct
16	Correct	90 ms	40184 KB	Output is correct
17	Correct	668 ms	39552 KB	Output is correct
18	Incorrect	315 ms	40184 KB	Output isn't correct

Subtask #3

21.4285714286 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	551 ms	39928 KB	Output is correct
2	Incorrect	562 ms	40056 KB	Output isn't correct
3	Correct	545 ms	40056 KB	Output is correct
4	Incorrect	663 ms	39816 KB	Output isn't correct
5	Correct	351 ms	40440 KB	Output is correct
6	Incorrect	664 ms	39928 KB	Output isn't correct
7	Correct	424 ms	40312 KB	Output is correct
8	Correct	551 ms	39928 KB	Output is correct
9	Correct	549 ms	39928 KB	Output is correct
10	Incorrect	637 ms	39672 KB	Output isn't correct
11	Incorrect	646 ms	39552 KB	Output isn't correct
12	Incorrect	648 ms	39552 KB	Output isn't correct
13	Incorrect	583 ms	40056 KB	Output isn't correct
14	Incorrect	848 ms	40056 KB	Output isn't correct
15	Incorrect	644 ms	39672 KB	Output isn't correct
16	Incorrect	647 ms	39672 KB	Output isn't correct
17	Incorrect	547 ms	39808 KB	Output isn't correct
18	Incorrect	557 ms	39928 KB	Output isn't correct
19	Incorrect	554 ms	39672 KB	Output isn't correct
20	Correct	547 ms	40060 KB	Output is correct
21	Incorrect	802 ms	40056 KB	Output isn't correct
22	Correct	536 ms	40440 KB	Output is correct
23	Incorrect	567 ms	39928 KB	Output isn't correct
24	Incorrect	667 ms	39800 KB	Output isn't correct
25	Incorrect	693 ms	39928 KB	Output isn't correct
26	Incorrect	658 ms	39812 KB	Output isn't correct
27	Correct	512 ms	40312 KB	Output is correct
28	Incorrect	648 ms	39836 KB	Output isn't correct
29	Correct	534 ms	40440 KB	Output is correct
30	Correct	575 ms	40204 KB	Output is correct
31	Incorrect	614 ms	39800 KB	Output isn't correct
32	Incorrect	666 ms	39816 KB	Output isn't correct
33	Incorrect	642 ms	39800 KB	Output isn't correct
34	Correct	428 ms	40312 KB	Output is correct
35	Incorrect	649 ms	40056 KB	Output isn't correct
36	Correct	536 ms	40568 KB	Output is correct
37	Correct	349 ms	40440 KB	Output is correct
38	Incorrect	673 ms	39940 KB	Output isn't correct
39	Incorrect	669 ms	39800 KB	Output isn't correct
40	Incorrect	638 ms	39928 KB	Output isn't correct
41	Correct	192 ms	40312 KB	Output is correct
42	Incorrect	692 ms	39928 KB	Output isn't correct