oj.uz

답안 #155729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
155729 2019-09-30T06:55:32 Z Flying_dragon_02 Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 401 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int mod = 1e9 + 7;

const int inf = 1e9;

int add(int x, int y) {
    return (1ll * x + 1ll * y) % mod;
}

int del(int x, int y) {
    return ((1ll * x - 1ll * y) % mod + mod) % mod;
}

int mul(int x, int y) {
    return (1ll * x * 1ll * y) % mod;
}

const int N = 1e7 + 5;

int dp[2 * N];
bool used[N];
vector<int> vec[N];
int bit[2 * N];

void update(int x, int val) {
    while(x > 0) {
        bit[x] = min(bit[x], val);
        x -= x & (-x);
    }
}

int get(int x) {
    if(x == 0) return 0;
    int val = inf;
    while(x < N) {
        val = min(val, bit[x]);
        x += x & (-x);
    }
    return val;
}

int m, q;

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> m >> q;
    for(int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        if(used[x]) continue;
        used[x] = 1;
        for(int l = 0; l < N; l++) {
            if(x * l >= N) break;
            vec[x * l].pb(x);
        }
    }
    for(int i = 1; i <= N - 5; i++)
        bit[i] = dp[i] = inf;
    for(int i = 0; i <= N - 5; i++) {
        dp[i] = get(i);
        for(int j = 0; j < vec[i].size(); j++)
            update(i + vec[i][j] - 1, min(inf, dp[i] + 1));
        vec[i].clear();
    }
    for(int i = 1; i <= q; i++) {
        int x;
        cin >> x;
        if(dp[x] == inf)
            cout << "oo\n";
        else
            cout << dp[x] << "\n";
    }
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:71:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < vec[i].size(); j++)
                        ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 275 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 330 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 262 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 271 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 239 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 237 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 243 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 235 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 300 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 237 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 235 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 234 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 234 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 287 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 401 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 380 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 365 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 249 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 296 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 253 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 234 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 370 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 264 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 236 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 241 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 235 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 316 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 296 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 275 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 309 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 242 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 240 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 239 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 240 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 235 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 239 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 355 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 239 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 276 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 238 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 240 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 248 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 242 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 237 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 247 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 242 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 240 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 233 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 352 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 296 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 237 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 235 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 244 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 269 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 280 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 252 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 247 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 304 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 276 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 357 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 308 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 241 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 233 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)