Submission #443861

#	Time	Username	Problem	Language	Result	Execution time	Memory
443861		Khizri	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	101 ms	65540 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=2e5+5;
vector<pii>dp[mxn];
std::vector<int> find_subset(int l, int r, std::vector<int> vt) {
	bool q=false;
	int ans=-1,ind=-1;
    for(int i=0;i<vt.size();i++){
    	dp[i].pb({vt[i],-1});
    	if(l<=vt[i]&&vt[i]<=r){
    		return {i};
		}
		for(int j=0;j<i;j++){
			for(int k=0;k<dp[j].size();k++){
				dp[i].pb({dp[j][k].F+vt[i],j});
				if(l<=dp[j][k].F+vt[i]&&dp[j][k].F+vt[i]<=r){
					ans=dp[j][k].F+vt[i];
					ind=i;
					q=true;
					goto loopo;
				}
			}
		}
	}
	loopo:
	vector<int>v;
	if(!q){
		return v;
	}
	while(ind!=-1){
		//cout<<ans<<' '<<ind<<endl;
		v.pb(ind);
		//cout<<dp[ind].size()<<endl;
		for(int i=0;i<dp[ind].size();i++){
			//cout<<dp[ind][i].F<<' ';
			if(dp[ind][i].F==ans){
				ans-=vt[ind];
				ind=dp[ind][i].S;
				break;
			}
		}
		//cout<<endl;
	}
	//cout<<0<<endl;
	sort(all(v));
	return v;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<vt.size();i++){
      |                 ~^~~~~~~~~~
molecules.cpp:27:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    for(int k=0;k<dp[j].size();k++){
      |                ~^~~~~~~~~~~~~
molecules.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<dp[ind].size();i++){
      |               ~^~~~~~~~~~~~~~~

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