답안 #74563 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74563	2018-09-03T17:27:24 Z	SpeedOfMagic	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	1.11111 / 100	1000 ms	42716 KB

brunhilda

/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
template<typename T, typename U>  using hmap = __gnu_pbds::gp_hash_table<T, U>;
//#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
#define check(a) put #a << ": " << a << endl;
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here
//you want to set 2 functions: f(int a, int b) and segTreeNode::update(int val) and 1 parameter: nothing
 
const int nothing = 0; //nothing means that f(x, nothing) = x
 
struct segTreeNode {
    int val = nothing;
 
    segTreeNode(int _val) : val(_val) {}
 
    void update(int _val) { //function that updates node based on val
        this -> val = _val;
    }
};
 
vector<segTreeNode> segTree;
int n, tot;
 
int f(int a, int b) { //f - query you need to calculate, but for two values
    return max(segTree[a].val, segTree[b].val);
}
 
void update(int nodeToUpdate, int value, int cur = 1, int ll = 1, int rr = tot) {
    if (ll == rr) {
        segTree[cur].update(value);
        return;
    }
 
    int p = (ll + rr) / 2;
 
    if (nodeToUpdate <= p)
        update(nodeToUpdate, value, cur * 2, ll, p);
    else
        update(nodeToUpdate, value, cur * 2 + 1, p + 1, rr);
 
    segTree[cur] = f(cur * 2, cur * 2 + 1);
}
 
int query(int l, int r, int cur = 1, int ll = 1, int rr = tot) {
    if (l > r)
        return nothing;
 
    if (l == ll && r == rr)
        return segTree[cur].val;
 
    int mid = (ll + rr) / 2;
    return f(query(l, min(r, mid), cur * 2, ll, mid), query(max(l, mid + 1), r, cur * 2 + 1, mid + 1, rr));
}
 
void init(vector<int> vals) {
    n = vals.size();
 
    tot = n;
    while (tot & (tot - 1))
        tot++;
 
    segTree = vector<segTreeNode>(tot * 2, segTreeNode(nothing));
 
    for (int i = 0; i < n; i++)
        segTree[i + tot].val = vals[i];
 
    for (int i = tot - 1; i; i--)
        segTree[i] = f(i * 2, i * 2 + 1);
}
 
const long long N = 1e7 + 1;
const int LIM = 150;
int dp[N];
 
void run() {
    int m, q;
    read(m, q);
 
    vint primes;
 
    priority_queue<pair<int, int>> nxt;
    int p[m];
    rep(i, 0, m) {
        get p[i];
        if (p[i] > LIM)
            nxt.push({-p[i], i});
        else
            primes.pb(p[i]);
    }
 
    long long mul = 1;
    rep(i, 0, m) {
        mul *= p[i];
        if (mul > N) {
            mul = 1e9;
            break;
        }
    }
 
    dp[0] = 0;
    
    int pen = 0;
 
    init(vint(m, 1));
 
    rep(i, 1, N) {
        while (!nxt.empty() && -nxt.top().fs == i) {
            int j = nxt.top().sc;
            int val = -nxt.top().fs;
            nxt.pop();
            nxt.push({-(val + p[j]), j});
 
            update(j + 1, -pen);
        }
        int d = query(1, tot) + pen;
        dp[i] = dp[i - d] + 1;
 
        pen++;
    }
 
    rep(i, 0, q) {
        int n;
        get n;
        if (n >= mul)
            put "oo";
        else
            put dp[n];
        eol;
    }
}
int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
1.11111111111 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	55 ms	39548 KB	Output isn't correct
2	Incorrect	175 ms	39548 KB	Output isn't correct
3	Incorrect	53 ms	39608 KB	Output isn't correct
4	Incorrect	166 ms	39848 KB	Output isn't correct
5	Incorrect	54 ms	39848 KB	Output isn't correct
6	Incorrect	55 ms	39848 KB	Output isn't correct
7	Incorrect	53 ms	39872 KB	Output isn't correct
8	Incorrect	51 ms	39872 KB	Output isn't correct
9	Incorrect	52 ms	39872 KB	Output isn't correct
10	Incorrect	57 ms	39872 KB	Output isn't correct
11	Incorrect	55 ms	39872 KB	Output isn't correct
12	Correct	137 ms	39872 KB	Output is correct
13	Execution timed out	1083 ms	39872 KB	Time limit exceeded
14	Execution timed out	1084 ms	39872 KB	Time limit exceeded
15	Incorrect	115 ms	39872 KB	Output isn't correct
16	Incorrect	176 ms	39872 KB	Output isn't correct
17	Incorrect	247 ms	39900 KB	Output isn't correct
18	Incorrect	165 ms	39912 KB	Output isn't correct

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	466 ms	40092 KB	Output isn't correct
2	Incorrect	543 ms	42244 KB	Output isn't correct
3	Execution timed out	1063 ms	42244 KB	Time limit exceeded
4	Incorrect	648 ms	42244 KB	Output isn't correct
5	Execution timed out	1073 ms	42244 KB	Time limit exceeded
6	Incorrect	285 ms	42244 KB	Output isn't correct
7	Incorrect	470 ms	42244 KB	Output isn't correct
8	Incorrect	495 ms	42244 KB	Output isn't correct
9	Execution timed out	1080 ms	42244 KB	Time limit exceeded
10	Execution timed out	1083 ms	42244 KB	Time limit exceeded
11	Execution timed out	1073 ms	42244 KB	Time limit exceeded
12	Incorrect	701 ms	42244 KB	Output isn't correct
13	Incorrect	185 ms	42244 KB	Output isn't correct
14	Incorrect	626 ms	42244 KB	Output isn't correct
15	Execution timed out	1085 ms	42244 KB	Time limit exceeded
16	Incorrect	544 ms	42244 KB	Output isn't correct
17	Execution timed out	1076 ms	42244 KB	Time limit exceeded
18	Execution timed out	1071 ms	42244 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1073 ms	42244 KB	Time limit exceeded
2	Execution timed out	1083 ms	42244 KB	Time limit exceeded
3	Execution timed out	1067 ms	42244 KB	Time limit exceeded
4	Incorrect	868 ms	42244 KB	Output isn't correct
5	Execution timed out	1057 ms	42716 KB	Time limit exceeded
6	Execution timed out	1089 ms	42716 KB	Time limit exceeded
7	Execution timed out	1091 ms	42716 KB	Time limit exceeded
8	Execution timed out	1080 ms	42716 KB	Time limit exceeded
9	Execution timed out	1074 ms	42716 KB	Time limit exceeded
10	Execution timed out	1078 ms	42716 KB	Time limit exceeded
11	Execution timed out	1014 ms	42716 KB	Time limit exceeded
12	Execution timed out	1091 ms	42716 KB	Time limit exceeded
13	Execution timed out	1079 ms	42716 KB	Time limit exceeded
14	Incorrect	222 ms	42716 KB	Output isn't correct
15	Execution timed out	1084 ms	42716 KB	Time limit exceeded
16	Execution timed out	1079 ms	42716 KB	Time limit exceeded
17	Execution timed out	1075 ms	42716 KB	Time limit exceeded
18	Execution timed out	1083 ms	42716 KB	Time limit exceeded
19	Incorrect	297 ms	42716 KB	Output isn't correct
20	Execution timed out	1077 ms	42716 KB	Time limit exceeded
21	Incorrect	495 ms	42716 KB	Output isn't correct
22	Execution timed out	1082 ms	42716 KB	Time limit exceeded
23	Execution timed out	1074 ms	42716 KB	Time limit exceeded
24	Incorrect	450 ms	42716 KB	Output isn't correct
25	Execution timed out	1075 ms	42716 KB	Time limit exceeded
26	Incorrect	858 ms	42716 KB	Output isn't correct
27	Execution timed out	1076 ms	42716 KB	Time limit exceeded
28	Incorrect	418 ms	42716 KB	Output isn't correct
29	Execution timed out	1084 ms	42716 KB	Time limit exceeded
30	Execution timed out	1086 ms	42716 KB	Time limit exceeded
31	Incorrect	556 ms	42716 KB	Output isn't correct
32	Incorrect	800 ms	42716 KB	Output isn't correct
33	Incorrect	317 ms	42716 KB	Output isn't correct
34	Execution timed out	1070 ms	42716 KB	Time limit exceeded
35	Incorrect	615 ms	42716 KB	Output isn't correct
36	Execution timed out	1086 ms	42716 KB	Time limit exceeded
37	Execution timed out	1051 ms	42716 KB	Time limit exceeded
38	Execution timed out	1079 ms	42716 KB	Time limit exceeded
39	Incorrect	623 ms	42716 KB	Output isn't correct
40	Execution timed out	1086 ms	42716 KB	Time limit exceeded
41	Execution timed out	1084 ms	42716 KB	Time limit exceeded
42	Execution timed out	1084 ms	42716 KB	Time limit exceeded

답안 #74563

Compilation message

Subtask #1 1.11111111111 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
1.11111111111 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0