oj.uz

Submission #781365

# Submission time Handle Problem Language Result Execution time Memory
781365 2023-07-13T04:39:31 Z devariaota Detecting Molecules (IOI16_molecules) C++17
0 / 100
 33 ms 65536 KB 
#include "molecules.h"
#include <bits/stdc++.h>
// #define int long long
using namespace std;
vector <int> p;
int lower,up;
int memo[10005][10005];
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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -