Submission #156531

#	Time	Username	Problem	Language	Result	Execution time	Memory
156531		a_player	Detecting Molecules (IOI16_molecules)	C++14	19 / 100	2 ms	380 KiB

molecules

#include <bits/stdc++.h>

#define f first
#define s second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;

int dp[10001];
bitset<10001> vis;

vector<int> find_subset(int l,int u,vector<int> w){
	
	dp[0]=1;
	for(int i=0;i<w.size();i++)
	for(int j=u;j>=w[i];j--)if(dp[j-w[i]])dp[j]=1;
	int pos=-1;
		for(int i=l;i<=u;i++)if(dp[i])pos=i;
  vector<int> sol;
		if(pos==-1){
			return sol;
			}
  for(int h=0;h<2;h++)
		for(int i=w.size()-1;i>=0;i--)if(!vis[i])if(pos-w[i]>=0)if(dp[pos-w[i]]){
			pos-=w[i];
			sol.push_back(i);
          vis[i]=1;
		}
		
		
	return sol;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<w.size();i++)
              ~^~~~~~~~~

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