oj.uz

Submission #781336

# Submission time Handle Problem Language Result Execution time Memory
781336 2023-07-13T03:46:35 Z devariaota Detecting Molecules (IOI16_molecules) C++17
0 / 100
 1 ms 340 KB 
#include "molecules.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll memo[10005];
ll up,lower,v;
vector <int> ans;
int n;
vector <int > p;
ll dp (ll indeks){
    // cout<<indeks<<endl;
    if (indeks>=n) {
        memo[indeks]=0;
        return 0;
    }
    if (indeks==n-1){
        memo[indeks]=p[indeks];
        return p[indeks];
    }
    if (memo[indeks]!=-1) return memo[indeks];
    for (int i=indeks+1;i<=n;i++){
        memo[indeks]=max(dp(i),memo[indeks]);
        if (dp(i)+p[indeks]<=up){
            memo[indeks]=max(memo[indeks],dp(i)+p[indeks]);
        }
    }
    // cout<<indeks<<" "<<memo[indeks]<<endl;
    return memo[indeks];
}
void bt (ll indeks){
    if (indeks>=n) return;
    if (indeks==n-1){
        ans.push_back(n-1);
        return;
    }
    for (int i=indeks+1;i<n;i++){
        if (v==dp(i)){
            bt(i);
            break;
        }
        else if (v==dp(i)+p[indeks]){
            ans.push_back(indeks);
            bt(i);
            break;
        }
        // if (v==dp(i)+p[indeks]){
        //     ans.push_back(indeks);
        //     bt(i);
        //     break;
        // }
    }
}
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();
    p.push_back(0);

    v=dp(0);
    // cout<<v<<"::"<<dp(4)<<"::"<<n<<endl;
    if (v<l){
        return ans;
    }
    bt(0);
    return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB OK (n = 1, answer = NO)
2 Incorrect 1 ms 340 KB sum of weights should be in [10..12] but it is 13
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Contestant can not find answer, jury can
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB OK (n = 1, answer = NO)
2 Incorrect 1 ms 340 KB sum of weights should be in [10..12] but it is 13
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB OK (n = 1, answer = NO)
2 Incorrect 1 ms 340 KB sum of weights should be in [10..12] but it is 13
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB OK (n = 1, answer = NO)
2 Incorrect 1 ms 340 KB sum of weights should be in [10..12] but it is 13
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB OK (n = 1, answer = NO)
2 Incorrect 1 ms 340 KB sum of weights should be in [10..12] but it is 13
3 Halted 0 ms 0 KB -