| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 199491 | 2020-02-01T15:11:14 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<int> find_subset(long long l,long long u,vector<long long> w){
vector<pair<long long,int>> ww;
int n=w.size();
for(int i=0;i<n;i++){
ww.pb(mp(w[i],i));
}
sort(ww.begin(),ww.end());
long long pre[n];
long long s[n];
pre[0]=ww[0].a;
for(int i=1;i<n;i++){
pre[i]=pre[i-1]+ww[i].a;
}
s[n-1]=ww[n-1].a;
for(int i=n-2;i>=0;i--){
s[i]=s[i+1]+ww[i].a;
}
vector<int> ans;
for(int i=0;i<n;i++){
if(pre[i]<l and s[n-i-1]>=l){
int k=1;
//cout<<i<<endl;
while(true){
if(pre[k+i]-pre[k-1]<=u and pre[k+i]-pre[k-1]>=l){
for(int 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(int j=0;j<i+1;j++){
ans.pb(ww[j].b);
}
break;
}
}
return ans;
}