Submission #1020484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020484		vjudge1	Detecting Molecules (IOI16_molecules)	C++17	46 / 100	1073 ms	2616 KiB

molecules

#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

int dp[500100], d[500100];

vector<int> find_subset(int l, int u, vector<int> w) {
    d[0] = 1;
    dp[0] = -1;
    int MXW = 0;
    int dd = -1;
    for(int x: w){
        dd++;
        for(int i=MXW; i>=0; i--){
            if(!d[i]) continue;
            if(i + x > u) continue;
            MXW = max(MXW, i + x);
            if(d[i + x]) continue;
            d[i+x] = 1;
            dp[i + x] = dd;
        }
            
    }
    int ok = 0;
    vector<int> ans;
    for(int i=l; i<=u; i++){
        if(d[i]){
            map<int, int> us;
            int x = i;
            while(x != 0){
                if(us[dp[x]]) cout<<1/0;
                us[dp[x]] = 1;
                ans.pb(dp[x]);
                x -= w[dp[x]];
            }
            return ans;
        }
    }
    return ans;

}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:32:38: warning: division by zero [-Wdiv-by-zero]
   32 |                 if(us[dp[x]]) cout<<1/0;
      |                                     ~^~
molecules.cpp:25:9: warning: unused variable 'ok' [-Wunused-variable]
   25 |     int ok = 0;
      |         ^~

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31