oj.uz

답안 #138431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138431 2019-07-29T22:32:47 Z silxikys Brunhilda’s Birthday (BOI13_brunhilda) C++14
29.8413 / 100
 1000 ms 44532 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5+5, INF = 2e9+9;
int m, Q;

int dp[10000005];

vector<int> primes;

struct Bag
{
    multiset<int> ms;
    int aux = 0;
    int max() {
        return *ms.rbegin() + aux;
    }
    void delta(int x) {
        aux += x;
    }
    void insert(int x) {
        ms.insert(x-aux);
    }
    void remove(int x) {
        auto it = ms.find(x-aux);
        ms.erase(it);
    }
};

struct Bag2
{
    set<pair<int,int>> ms;
    int aux = 0;
    void delta(int x) {
        aux += x;
    }
    pair<int,int> min() {
        return {ms.begin()->first+aux,ms.begin()->second};
    }
    void pop() {
        ms.erase(ms.begin());
    }
    void insert(pair<int,int> p) {
        ms.insert({p.first-aux,p.second});
    }
};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> m >> Q;
    for (int i = 0; i < m; i++) {
        int p; cin >> p;
        primes.push_back(p);
    }
    sort(primes.begin(),primes.end());
    int maxPrime = primes.back();
    for (int i = 1; i < maxPrime; i++) {
        dp[i] = 1;
    }
    Bag bag;
    Bag2 mods;
    for (int p: primes) {
        bag.insert((maxPrime-1)%p);
        mods.insert({p-((maxPrime-1)%p),p});
    }
    int maxQ = 0;
    vector<int> queries;
    while (Q--) {
        int qi; cin >> qi;
        queries.push_back(qi);
        maxQ = max(maxQ,qi);
    }
    for (int i = maxPrime; i <= maxQ; i++) {
        bag.delta(1);
        mods.delta(-1);
        while (mods.min().first == 0) {
            int p = mods.min().second;
            mods.pop();
            mods.insert({p,p});
            bag.remove(p);
            bag.insert(0);
        }

        dp[i] = INF;
        int mxmod = bag.max();
        dp[i] = min(dp[i],1+dp[i-mxmod]);
        
        /*
        cout << i << " : " << mxmod << ' ';
        int mx = 0;
        for (int p: primes) {
            mx = max(mx,i%p);
        }
        cout << mx << '\n';
        */
    }

    /*
    for (int i = 1; i <= 50; i++) {
        cout << i << ": " << dp[i] << '\n';
    }
    */

    for (int qi: queries) {
        if (dp[qi] == INF) cout << "oo\n";
        else cout << dp[qi] << '\n';
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 424 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 2 ms 424 KB Output is correct
13 Correct 4 ms 504 KB Output is correct
14 Correct 4 ms 632 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 4 ms 376 KB Output is correct
17 Correct 5 ms 508 KB Output is correct
18 Correct 4 ms 508 KB Output is correct

Subtask #2
5.55555555556 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1068 ms 39328 KB Time limit exceeded
2 Correct 91 ms 44532 KB Output is correct
3 Execution timed out 1082 ms 19000 KB Time limit exceeded
4 Execution timed out 1078 ms 19288 KB Time limit exceeded
5 Execution timed out 1080 ms 14764 KB Time limit exceeded
6 Correct 691 ms 14112 KB Output is correct
7 Execution timed out 1083 ms 38668 KB Time limit exceeded
8 Correct 694 ms 15256 KB Output is correct
9 Execution timed out 1068 ms 15836 KB Time limit exceeded
10 Execution timed out 1082 ms 19204 KB Time limit exceeded
11 Execution timed out 1079 ms 10324 KB Time limit exceeded
12 Execution timed out 1073 ms 9356 KB Time limit exceeded
13 Correct 895 ms 39416 KB Output is correct
14 Execution timed out 1070 ms 19448 KB Time limit exceeded
15 Execution timed out 1084 ms 10888 KB Time limit exceeded
16 Correct 94 ms 44532 KB Output is correct
17 Execution timed out 1078 ms 5144 KB Time limit exceeded
18 Execution timed out 1064 ms 32260 KB Time limit exceeded

Subtask #3
4.28571428571 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1072 ms 12304 KB Time limit exceeded
2 Execution timed out 1079 ms 10872 KB Time limit exceeded
3 Execution timed out 1076 ms 11640 KB Time limit exceeded
4 Execution timed out 1081 ms 9340 KB Time limit exceeded
5 Execution timed out 1081 ms 40916 KB Time limit exceeded
6 Execution timed out 1079 ms 6620 KB Time limit exceeded
7 Execution timed out 1084 ms 26356 KB Time limit exceeded
8 Execution timed out 1076 ms 12596 KB Time limit exceeded
9 Execution timed out 1080 ms 12604 KB Time limit exceeded
10 Execution timed out 1068 ms 8508 KB Time limit exceeded
11 Execution timed out 1073 ms 11272 KB Time limit exceeded
12 Execution timed out 1070 ms 6232 KB Time limit exceeded
13 Execution timed out 1069 ms 9832 KB Time limit exceeded
14 Execution timed out 1075 ms 9364 KB Time limit exceeded
15 Execution timed out 1077 ms 5672 KB Time limit exceeded
16 Execution timed out 1075 ms 5124 KB Time limit exceeded
17 Execution timed out 1075 ms 11852 KB Time limit exceeded
18 Execution timed out 1083 ms 10924 KB Time limit exceeded
19 Execution timed out 1077 ms 32100 KB Time limit exceeded
20 Execution timed out 1075 ms 11860 KB Time limit exceeded
21 Execution timed out 1075 ms 7284 KB Time limit exceeded
22 Execution timed out 1084 ms 18608 KB Time limit exceeded
23 Execution timed out 1078 ms 21832 KB Time limit exceeded
24 Correct 883 ms 40384 KB Output is correct
25 Execution timed out 1073 ms 8664 KB Time limit exceeded
26 Execution timed out 1080 ms 9328 KB Time limit exceeded
27 Execution timed out 1078 ms 18812 KB Time limit exceeded
28 Execution timed out 1072 ms 31308 KB Time limit exceeded
29 Execution timed out 1079 ms 19240 KB Time limit exceeded
30 Execution timed out 1073 ms 15060 KB Time limit exceeded
31 Execution timed out 1070 ms 22468 KB Time limit exceeded
32 Execution timed out 1078 ms 17000 KB Time limit exceeded
33 Correct 503 ms 40364 KB Output is correct
34 Execution timed out 1085 ms 26336 KB Time limit exceeded
35 Execution timed out 1090 ms 26480 KB Time limit exceeded
36 Execution timed out 1076 ms 17880 KB Time limit exceeded
37 Execution timed out 1083 ms 40940 KB Time limit exceeded
38 Execution timed out 1080 ms 6708 KB Time limit exceeded
39 Execution timed out 1077 ms 35212 KB Time limit exceeded
40 Execution timed out 1076 ms 8148 KB Time limit exceeded
41 Correct 103 ms 39668 KB Output is correct
42 Execution timed out 1080 ms 5492 KB Time limit exceeded