| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 199412 | 2020-02-01T10:17:41 Z | kshitij_sodani | Detecting Molecules (IOI16_molecules) | C++17 | 0 ms | 0 KB |
#include <iostream>
#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
typedef long long int llo ;
#define mp make_pair
#define pb push_back
#define a first
#define b second
vector<llo> find_subset(llo l,llo u,vector<llo> w){
vector<pair<llo,llo>> ww;
llo n=w.size();
for(int i=0;i<n;i++){
ww.pb(mp(w[i],i));
}
sort(ww.begin(),ww.end());
llo pre[n];
llo s[n];
pre[0]=ww[0].a;
for(llo i=1;i<n;i++){
pre[i]=pre[i-1]+ww[i].a;
}
s[n-1]=ww[n-1].a;
for(llo i=n-2;i>=0;i--){
s[i]=s[i+1]+ww[i].a;
}
vector<llo> ans;
for(llo i=0;i<n;i++){
if(pre[i]<l and s[n-i-1]>=l){
llo k=1;
//cout<<i<<endl;
while(true){
if(pre[k+i]-pre[k-1]<=u and pre[k+i]-pre[k-1]>=l){
for(llo j=k;j<k+i+1;j++){
ans.pb(ww[j].b);
}
break;
}
else{
k+=1;
}
}
break;
}
else if(pre[i]>=l and pre[i]<=u){
for(llo j=0;j<i+1;j++){
ans.pb(ww[j].b);
}
break;
}
}
return ans;
}
/*
llo main(){
vector<llo> ss=find_subset(15,17,{6,8,8,7});
for(llo i=0;i<ss.size();i++){
cout<<ss[i]<<" ";
}
cout<<endl;
return 0;
}*/