oj.uz

Submission #781369

# Submission time Handle Problem Language Result Execution time Memory
781369 2023-07-13T04:44:30 Z makanhulia Detecting Molecules (IOI16_molecules) C++17
31 / 100
 2 ms 1492 KB 
#include "molecules.h"
#include <bits/stdc++.h>
// #define int long long
using namespace std;
vector <int> p;
int lower,up;
int memo[100][1005];
vector<int> ans;
int n,v;
int dp (int indeks, int sisa){
    if (indeks>=n) return 0;
    if (memo[indeks][sisa]!=-1) return memo[indeks][sisa];
    memo[indeks][sisa]=dp(indeks+1,sisa);
    if (sisa-p[indeks]>=0){
        memo[indeks][sisa]=max(memo[indeks][sisa],p[indeks]+dp(indeks+1,sisa-p[indeks]));
    }
    return memo[indeks][sisa];
}
void bt (int indeks, int sisa){
    if (indeks>=n) return;
    if (dp(indeks,sisa)==dp(indeks+1,sisa)){
        bt(indeks+1,sisa);
    }
    else{
        ans.push_back(indeks);
        bt(indeks+1,sisa-p[indeks]);
    }
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
    memset(memo,-1,sizeof(memo));
    p=w;
    lower=l,up=u;
    n=w.size();
    v=dp(0,u);
    // cout<<v<<"::"<<"::"<<n<<endl;
    if (v<l){
        return ans;
    }
    bt(0,u);
    return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB OK (n = 1, answer = NO)
2 Correct 1 ms 596 KB OK (n = 1, answer = NO)
3 Correct 1 ms 596 KB OK (n = 1, answer = YES)
4 Correct 1 ms 688 KB OK (n = 2, answer = YES)
5 Correct 1 ms 596 KB OK (n = 2, answer = YES)
6 Correct 1 ms 596 KB OK (n = 3, answer = YES)
7 Correct 1 ms 596 KB OK (n = 3, answer = YES)
8 Correct 1 ms 688 KB OK (n = 3, answer = YES)
9 Correct 1 ms 596 KB OK (n = 3, answer = YES)
10 Correct 1 ms 688 KB OK (n = 3, answer = YES)
11 Correct 1 ms 596 KB OK (n = 3, answer = YES)
12 Correct 1 ms 596 KB OK (n = 3, answer = YES)
13 Correct 1 ms 596 KB OK (n = 3, answer = NO)
14 Correct 1 ms 688 KB OK (n = 3, answer = YES)
15 Correct 1 ms 688 KB OK (n = 3, answer = YES)
16 Correct 1 ms 596 KB OK (n = 3, answer = NO)
17 Correct 1 ms 688 KB OK (n = 3, answer = NO)
18 Correct 1 ms 692 KB OK (n = 100, answer = NO)
19 Correct 1 ms 692 KB OK (n = 100, answer = YES)

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB OK (n = 12, answer = YES)
2 Correct 1 ms 596 KB OK (n = 12, answer = YES)
3 Correct 1 ms 596 KB OK (n = 12, answer = NO)
4 Correct 1 ms 596 KB OK (n = 12, answer = NO)
5 Correct 1 ms 596 KB OK (n = 12, answer = YES)
6 Correct 1 ms 688 KB OK (n = 12, answer = YES)
7 Correct 1 ms 596 KB OK (n = 12, answer = YES)
8 Correct 1 ms 596 KB OK (n = 12, answer = YES)
9 Correct 1 ms 596 KB OK (n = 6, answer = YES)
10 Correct 1 ms 596 KB OK (n = 12, answer = YES)
11 Correct 1 ms 596 KB OK (n = 100, answer = NO)
12 Correct 1 ms 596 KB OK (n = 100, answer = YES)
13 Correct 1 ms 596 KB OK (n = 100, answer = NO)
14 Correct 1 ms 596 KB OK (n = 100, answer = YES)
15 Correct 1 ms 596 KB OK (n = 100, answer = YES)
16 Correct 1 ms 596 KB OK (n = 100, answer = YES)
17 Correct 1 ms 596 KB OK (n = 100, answer = YES)

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB OK (n = 1, answer = NO)
2 Correct 1 ms 596 KB OK (n = 1, answer = NO)
3 Correct 1 ms 596 KB OK (n = 1, answer = YES)
4 Correct 1 ms 688 KB OK (n = 2, answer = YES)
5 Correct 1 ms 596 KB OK (n = 2, answer = YES)
6 Correct 1 ms 596 KB OK (n = 3, answer = YES)
7 Correct 1 ms 596 KB OK (n = 3, answer = YES)
8 Correct 1 ms 688 KB OK (n = 3, answer = YES)
9 Correct 1 ms 596 KB OK (n = 3, answer = YES)
10 Correct 1 ms 688 KB OK (n = 3, answer = YES)
11 Correct 1 ms 596 KB OK (n = 3, answer = YES)
12 Correct 1 ms 596 KB OK (n = 3, answer = YES)
13 Correct 1 ms 596 KB OK (n = 3, answer = NO)
14 Correct 1 ms 688 KB OK (n = 3, answer = YES)
15 Correct 1 ms 688 KB OK (n = 3, answer = YES)
16 Correct 1 ms 596 KB OK (n = 3, answer = NO)
17 Correct 1 ms 688 KB OK (n = 3, answer = NO)
18 Correct 1 ms 692 KB OK (n = 100, answer = NO)
19 Correct 1 ms 692 KB OK (n = 100, answer = YES)
20 Correct 1 ms 596 KB OK (n = 12, answer = YES)
21 Correct 1 ms 596 KB OK (n = 12, answer = YES)
22 Correct 1 ms 596 KB OK (n = 12, answer = NO)
23 Correct 1 ms 596 KB OK (n = 12, answer = NO)
24 Correct 1 ms 596 KB OK (n = 12, answer = YES)
25 Correct 1 ms 688 KB OK (n = 12, answer = YES)
26 Correct 1 ms 596 KB OK (n = 12, answer = YES)
27 Correct 1 ms 596 KB OK (n = 12, answer = YES)
28 Correct 1 ms 596 KB OK (n = 6, answer = YES)
29 Correct 1 ms 596 KB OK (n = 12, answer = YES)
30 Correct 1 ms 596 KB OK (n = 100, answer = NO)
31 Correct 1 ms 596 KB OK (n = 100, answer = YES)
32 Correct 1 ms 596 KB OK (n = 100, answer = NO)
33 Correct 1 ms 596 KB OK (n = 100, answer = YES)
34 Correct 1 ms 596 KB OK (n = 100, answer = YES)
35 Correct 1 ms 596 KB OK (n = 100, answer = YES)
36 Correct 1 ms 596 KB OK (n = 100, answer = YES)
37 Correct 1 ms 596 KB OK (n = 28, answer = YES)
38 Correct 1 ms 688 KB OK (n = 27, answer = YES)
39 Correct 1 ms 596 KB OK (n = 90, answer = YES)
40 Correct 1 ms 596 KB OK (n = 100, answer = YES)
41 Correct 1 ms 596 KB OK (n = 100, answer = YES)
42 Correct 1 ms 596 KB OK (n = 10, answer = YES)
43 Correct 1 ms 596 KB OK (n = 100, answer = YES)
44 Correct 1 ms 596 KB OK (n = 100, answer = YES)
45 Correct 1 ms 596 KB OK (n = 100, answer = YES)
46 Correct 1 ms 596 KB OK (n = 100, answer = YES)
47 Correct 1 ms 692 KB OK (n = 100, answer = NO)
48 Correct 1 ms 596 KB OK (n = 100, answer = NO)
49 Correct 1 ms 688 KB OK (n = 100, answer = NO)
50 Correct 1 ms 692 KB OK (n = 100, answer = YES)
51 Correct 1 ms 696 KB OK (n = 100, answer = YES)
52 Correct 1 ms 596 KB OK (n = 100, answer = YES)
53 Correct 1 ms 696 KB OK (n = 100, answer = YES)
54 Correct 1 ms 596 KB OK (n = 100, answer = YES)

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB OK (n = 1, answer = NO)
2 Correct 1 ms 596 KB OK (n = 1, answer = NO)
3 Correct 1 ms 596 KB OK (n = 1, answer = YES)
4 Correct 1 ms 688 KB OK (n = 2, answer = YES)
5 Correct 1 ms 596 KB OK (n = 2, answer = YES)
6 Correct 1 ms 596 KB OK (n = 3, answer = YES)
7 Correct 1 ms 596 KB OK (n = 3, answer = YES)
8 Correct 1 ms 688 KB OK (n = 3, answer = YES)
9 Correct 1 ms 596 KB OK (n = 3, answer = YES)
10 Correct 1 ms 688 KB OK (n = 3, answer = YES)
11 Correct 1 ms 596 KB OK (n = 3, answer = YES)
12 Correct 1 ms 596 KB OK (n = 3, answer = YES)
13 Correct 1 ms 596 KB OK (n = 3, answer = NO)
14 Correct 1 ms 688 KB OK (n = 3, answer = YES)
15 Correct 1 ms 688 KB OK (n = 3, answer = YES)
16 Correct 1 ms 596 KB OK (n = 3, answer = NO)
17 Correct 1 ms 688 KB OK (n = 3, answer = NO)
18 Correct 1 ms 692 KB OK (n = 100, answer = NO)
19 Correct 1 ms 692 KB OK (n = 100, answer = YES)
20 Correct 1 ms 596 KB OK (n = 12, answer = YES)
21 Correct 1 ms 596 KB OK (n = 12, answer = YES)
22 Correct 1 ms 596 KB OK (n = 12, answer = NO)
23 Correct 1 ms 596 KB OK (n = 12, answer = NO)
24 Correct 1 ms 596 KB OK (n = 12, answer = YES)
25 Correct 1 ms 688 KB OK (n = 12, answer = YES)
26 Correct 1 ms 596 KB OK (n = 12, answer = YES)
27 Correct 1 ms 596 KB OK (n = 12, answer = YES)
28 Correct 1 ms 596 KB OK (n = 6, answer = YES)
29 Correct 1 ms 596 KB OK (n = 12, answer = YES)
30 Correct 1 ms 596 KB OK (n = 100, answer = NO)
31 Correct 1 ms 596 KB OK (n = 100, answer = YES)
32 Correct 1 ms 596 KB OK (n = 100, answer = NO)
33 Correct 1 ms 596 KB OK (n = 100, answer = YES)
34 Correct 1 ms 596 KB OK (n = 100, answer = YES)
35 Correct 1 ms 596 KB OK (n = 100, answer = YES)
36 Correct 1 ms 596 KB OK (n = 100, answer = YES)
37 Correct 1 ms 596 KB OK (n = 28, answer = YES)
38 Correct 1 ms 688 KB OK (n = 27, answer = YES)
39 Correct 1 ms 596 KB OK (n = 90, answer = YES)
40 Correct 1 ms 596 KB OK (n = 100, answer = YES)
41 Correct 1 ms 596 KB OK (n = 100, answer = YES)
42 Correct 1 ms 596 KB OK (n = 10, answer = YES)
43 Correct 1 ms 596 KB OK (n = 100, answer = YES)
44 Correct 1 ms 596 KB OK (n = 100, answer = YES)
45 Correct 1 ms 596 KB OK (n = 100, answer = YES)
46 Correct 1 ms 596 KB OK (n = 100, answer = YES)
47 Correct 1 ms 692 KB OK (n = 100, answer = NO)
48 Correct 1 ms 596 KB OK (n = 100, answer = NO)
49 Correct 1 ms 688 KB OK (n = 100, answer = NO)
50 Correct 1 ms 692 KB OK (n = 100, answer = YES)
51 Correct 1 ms 696 KB OK (n = 100, answer = YES)
52 Correct 1 ms 596 KB OK (n = 100, answer = YES)
53 Correct 1 ms 696 KB OK (n = 100, answer = YES)
54 Correct 1 ms 596 KB OK (n = 100, answer = YES)
55 Runtime error 2 ms 1492 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB OK (n = 1, answer = NO)
2 Correct 1 ms 596 KB OK (n = 1, answer = NO)
3 Correct 1 ms 596 KB OK (n = 1, answer = YES)
4 Correct 1 ms 688 KB OK (n = 2, answer = YES)
5 Correct 1 ms 596 KB OK (n = 2, answer = YES)
6 Correct 1 ms 596 KB OK (n = 3, answer = YES)
7 Correct 1 ms 596 KB OK (n = 3, answer = YES)
8 Correct 1 ms 688 KB OK (n = 3, answer = YES)
9 Correct 1 ms 596 KB OK (n = 3, answer = YES)
10 Correct 1 ms 688 KB OK (n = 3, answer = YES)
11 Correct 1 ms 596 KB OK (n = 3, answer = YES)
12 Correct 1 ms 596 KB OK (n = 3, answer = YES)
13 Correct 1 ms 596 KB OK (n = 3, answer = NO)
14 Correct 1 ms 688 KB OK (n = 3, answer = YES)
15 Correct 1 ms 688 KB OK (n = 3, answer = YES)
16 Correct 1 ms 596 KB OK (n = 3, answer = NO)
17 Correct 1 ms 688 KB OK (n = 3, answer = NO)
18 Correct 1 ms 692 KB OK (n = 100, answer = NO)
19 Correct 1 ms 692 KB OK (n = 100, answer = YES)
20 Correct 1 ms 596 KB OK (n = 12, answer = YES)
21 Correct 1 ms 596 KB OK (n = 12, answer = YES)
22 Correct 1 ms 596 KB OK (n = 12, answer = NO)
23 Correct 1 ms 596 KB OK (n = 12, answer = NO)
24 Correct 1 ms 596 KB OK (n = 12, answer = YES)
25 Correct 1 ms 688 KB OK (n = 12, answer = YES)
26 Correct 1 ms 596 KB OK (n = 12, answer = YES)
27 Correct 1 ms 596 KB OK (n = 12, answer = YES)
28 Correct 1 ms 596 KB OK (n = 6, answer = YES)
29 Correct 1 ms 596 KB OK (n = 12, answer = YES)
30 Correct 1 ms 596 KB OK (n = 100, answer = NO)
31 Correct 1 ms 596 KB OK (n = 100, answer = YES)
32 Correct 1 ms 596 KB OK (n = 100, answer = NO)
33 Correct 1 ms 596 KB OK (n = 100, answer = YES)
34 Correct 1 ms 596 KB OK (n = 100, answer = YES)
35 Correct 1 ms 596 KB OK (n = 100, answer = YES)
36 Correct 1 ms 596 KB OK (n = 100, answer = YES)
37 Correct 1 ms 596 KB OK (n = 28, answer = YES)
38 Correct 1 ms 688 KB OK (n = 27, answer = YES)
39 Correct 1 ms 596 KB OK (n = 90, answer = YES)
40 Correct 1 ms 596 KB OK (n = 100, answer = YES)
41 Correct 1 ms 596 KB OK (n = 100, answer = YES)
42 Correct 1 ms 596 KB OK (n = 10, answer = YES)
43 Correct 1 ms 596 KB OK (n = 100, answer = YES)
44 Correct 1 ms 596 KB OK (n = 100, answer = YES)
45 Correct 1 ms 596 KB OK (n = 100, answer = YES)
46 Correct 1 ms 596 KB OK (n = 100, answer = YES)
47 Correct 1 ms 692 KB OK (n = 100, answer = NO)
48 Correct 1 ms 596 KB OK (n = 100, answer = NO)
49 Correct 1 ms 688 KB OK (n = 100, answer = NO)
50 Correct 1 ms 692 KB OK (n = 100, answer = YES)
51 Correct 1 ms 696 KB OK (n = 100, answer = YES)
52 Correct 1 ms 596 KB OK (n = 100, answer = YES)
53 Correct 1 ms 696 KB OK (n = 100, answer = YES)
54 Correct 1 ms 596 KB OK (n = 100, answer = YES)
55 Runtime error 2 ms 1492 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB OK (n = 1, answer = NO)
2 Correct 1 ms 596 KB OK (n = 1, answer = NO)
3 Correct 1 ms 596 KB OK (n = 1, answer = YES)
4 Correct 1 ms 688 KB OK (n = 2, answer = YES)
5 Correct 1 ms 596 KB OK (n = 2, answer = YES)
6 Correct 1 ms 596 KB OK (n = 3, answer = YES)
7 Correct 1 ms 596 KB OK (n = 3, answer = YES)
8 Correct 1 ms 688 KB OK (n = 3, answer = YES)
9 Correct 1 ms 596 KB OK (n = 3, answer = YES)
10 Correct 1 ms 688 KB OK (n = 3, answer = YES)
11 Correct 1 ms 596 KB OK (n = 3, answer = YES)
12 Correct 1 ms 596 KB OK (n = 3, answer = YES)
13 Correct 1 ms 596 KB OK (n = 3, answer = NO)
14 Correct 1 ms 688 KB OK (n = 3, answer = YES)
15 Correct 1 ms 688 KB OK (n = 3, answer = YES)
16 Correct 1 ms 596 KB OK (n = 3, answer = NO)
17 Correct 1 ms 688 KB OK (n = 3, answer = NO)
18 Correct 1 ms 692 KB OK (n = 100, answer = NO)
19 Correct 1 ms 692 KB OK (n = 100, answer = YES)
20 Correct 1 ms 596 KB OK (n = 12, answer = YES)
21 Correct 1 ms 596 KB OK (n = 12, answer = YES)
22 Correct 1 ms 596 KB OK (n = 12, answer = NO)
23 Correct 1 ms 596 KB OK (n = 12, answer = NO)
24 Correct 1 ms 596 KB OK (n = 12, answer = YES)
25 Correct 1 ms 688 KB OK (n = 12, answer = YES)
26 Correct 1 ms 596 KB OK (n = 12, answer = YES)
27 Correct 1 ms 596 KB OK (n = 12, answer = YES)
28 Correct 1 ms 596 KB OK (n = 6, answer = YES)
29 Correct 1 ms 596 KB OK (n = 12, answer = YES)
30 Correct 1 ms 596 KB OK (n = 100, answer = NO)
31 Correct 1 ms 596 KB OK (n = 100, answer = YES)
32 Correct 1 ms 596 KB OK (n = 100, answer = NO)
33 Correct 1 ms 596 KB OK (n = 100, answer = YES)
34 Correct 1 ms 596 KB OK (n = 100, answer = YES)
35 Correct 1 ms 596 KB OK (n = 100, answer = YES)
36 Correct 1 ms 596 KB OK (n = 100, answer = YES)
37 Correct 1 ms 596 KB OK (n = 28, answer = YES)
38 Correct 1 ms 688 KB OK (n = 27, answer = YES)
39 Correct 1 ms 596 KB OK (n = 90, answer = YES)
40 Correct 1 ms 596 KB OK (n = 100, answer = YES)
41 Correct 1 ms 596 KB OK (n = 100, answer = YES)
42 Correct 1 ms 596 KB OK (n = 10, answer = YES)
43 Correct 1 ms 596 KB OK (n = 100, answer = YES)
44 Correct 1 ms 596 KB OK (n = 100, answer = YES)
45 Correct 1 ms 596 KB OK (n = 100, answer = YES)
46 Correct 1 ms 596 KB OK (n = 100, answer = YES)
47 Correct 1 ms 692 KB OK (n = 100, answer = NO)
48 Correct 1 ms 596 KB OK (n = 100, answer = NO)
49 Correct 1 ms 688 KB OK (n = 100, answer = NO)
50 Correct 1 ms 692 KB OK (n = 100, answer = YES)
51 Correct 1 ms 696 KB OK (n = 100, answer = YES)
52 Correct 1 ms 596 KB OK (n = 100, answer = YES)
53 Correct 1 ms 696 KB OK (n = 100, answer = YES)
54 Correct 1 ms 596 KB OK (n = 100, answer = YES)
55 Runtime error 2 ms 1492 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -