oj.uz

Submission #1109609

# Submission time Handle Problem Language Result Execution time Memory
1109609 2024-11-07T07:04:19 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 53 ms 19784 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }
const int mod = 1e9 +7, sze = 1e5 +10, inf = INT_MAX, LG = 20;
int dp[sze];
vector<pair<int,int>> event[sze];
void fast(){
    for(int i=1;i<sze;i++){
        dp[i]=inf;
    }
    int n,q;
    cin>>n>>q;
    multiset<int> ans; 
    int mx = 0;
    for(int i=1;i<=n;i++){
        int p;cin>>p;
        event[p].pb({p,p});
        mx=max(mx,p);
    }
    for(int i =1;i<sze;i++){
        for(auto v:event[i]){
            if(ans.find(dp[v.first]) !=ans.end() ){
                ans.erase(ans.find(dp[v.first]));
            }
        }
        if( i < mx ){
            dp[i]=1;
        }
        else if(!ans.empty()){
            dp[i]= (*ans.begin())+1;
        }
        if(dp[i]<inf){
            for(auto v:event[i]){
                ans.ins(dp[i]);
                if(i + v.second < sze){
                    event[i + v.second].pb({i,v.second});
                }
            }
        }
    }
 
 
    while(q--){
        int v;
        cin>>v;
        if(dp[v]>=inf){
            cout<<"oo"<<endl;
        }
        else{
            cout<<dp[v]<<endl;
        }
    }
}
 
signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3408 KB Output is correct
2 Correct 17 ms 6224 KB Output is correct
3 Correct 8 ms 5652 KB Output is correct
4 Correct 19 ms 3748 KB Output is correct
5 Correct 5 ms 4432 KB Output is correct
6 Correct 4 ms 3408 KB Output is correct
7 Correct 8 ms 5712 KB Output is correct
8 Correct 12 ms 6492 KB Output is correct
9 Correct 16 ms 7248 KB Output is correct
10 Correct 20 ms 7516 KB Output is correct
11 Correct 15 ms 6480 KB Output is correct
12 Correct 3 ms 3732 KB Output is correct
13 Correct 37 ms 9296 KB Output is correct
14 Correct 52 ms 9312 KB Output is correct
15 Correct 16 ms 6224 KB Output is correct
16 Correct 15 ms 6180 KB Output is correct
17 Correct 22 ms 4432 KB Output is correct
18 Correct 19 ms 3664 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 7004 KB Execution killed with signal 11
2 Runtime error 6 ms 6992 KB Execution killed with signal 11
3 Runtime error 9 ms 7248 KB Execution killed with signal 11
4 Runtime error 17 ms 10076 KB Execution killed with signal 11
5 Runtime error 8 ms 6992 KB Execution killed with signal 11
6 Runtime error 19 ms 11088 KB Execution killed with signal 11
7 Runtime error 7 ms 6992 KB Execution killed with signal 11
8 Runtime error 16 ms 9484 KB Execution killed with signal 11
9 Runtime error 8 ms 7248 KB Execution killed with signal 11
10 Runtime error 9 ms 7248 KB Execution killed with signal 11
11 Runtime error 10 ms 7248 KB Execution killed with signal 11
12 Runtime error 31 ms 13648 KB Execution killed with signal 11
13 Runtime error 6 ms 6736 KB Execution killed with signal 11
14 Runtime error 16 ms 10064 KB Execution killed with signal 11
15 Runtime error 8 ms 7248 KB Execution killed with signal 11
16 Runtime error 7 ms 6940 KB Execution killed with signal 11
17 Runtime error 47 ms 18792 KB Execution killed with signal 11
18 Runtime error 7 ms 7248 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7248 KB Execution killed with signal 11
2 Runtime error 8 ms 7248 KB Execution killed with signal 11
3 Runtime error 10 ms 7248 KB Execution killed with signal 11
4 Runtime error 31 ms 14412 KB Execution killed with signal 11
5 Runtime error 6 ms 6992 KB Execution killed with signal 11
6 Runtime error 8 ms 7304 KB Execution killed with signal 11
7 Runtime error 7 ms 7248 KB Execution killed with signal 11
8 Runtime error 8 ms 7248 KB Execution killed with signal 11
9 Runtime error 8 ms 7208 KB Execution killed with signal 11
10 Runtime error 30 ms 13648 KB Execution killed with signal 11
11 Runtime error 21 ms 11856 KB Execution killed with signal 11
12 Runtime error 45 ms 16968 KB Execution killed with signal 11
13 Runtime error 8 ms 7248 KB Execution killed with signal 11
14 Runtime error 31 ms 15548 KB Execution killed with signal 11
15 Runtime error 46 ms 18760 KB Execution killed with signal 11
16 Runtime error 53 ms 19784 KB Execution killed with signal 11
17 Runtime error 8 ms 7248 KB Execution killed with signal 11
18 Runtime error 9 ms 7248 KB Execution killed with signal 11
19 Runtime error 7 ms 6736 KB Execution killed with signal 11
20 Runtime error 9 ms 7408 KB Execution killed with signal 11
21 Runtime error 38 ms 16712 KB Execution killed with signal 11
22 Runtime error 8 ms 7248 KB Execution killed with signal 11
23 Runtime error 7 ms 6952 KB Execution killed with signal 11
24 Runtime error 10 ms 8016 KB Execution killed with signal 11
25 Runtime error 38 ms 14168 KB Execution killed with signal 11
26 Runtime error 33 ms 14408 KB Execution killed with signal 11
27 Runtime error 9 ms 7504 KB Execution killed with signal 11
28 Runtime error 6 ms 6736 KB Execution killed with signal 11
29 Runtime error 8 ms 7248 KB Execution killed with signal 11
30 Runtime error 8 ms 7248 KB Execution killed with signal 11
31 Runtime error 6 ms 6992 KB Execution killed with signal 11
32 Runtime error 19 ms 10576 KB Execution killed with signal 11
33 Runtime error 6 ms 6736 KB Execution killed with signal 11
34 Runtime error 7 ms 7248 KB Execution killed with signal 11
35 Runtime error 6 ms 6868 KB Execution killed with signal 11
36 Runtime error 8 ms 7416 KB Execution killed with signal 11
37 Runtime error 8 ms 6992 KB Execution killed with signal 11
38 Runtime error 8 ms 7248 KB Execution killed with signal 11
39 Runtime error 7 ms 6992 KB Execution killed with signal 11
40 Runtime error 7 ms 7016 KB Execution killed with signal 11
41 Runtime error 8 ms 7004 KB Execution killed with signal 11
42 Runtime error 51 ms 19540 KB Execution killed with signal 11