제출 #1365875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365875		stanirina	Detecting Molecules (IOI16_molecules)	C++20	100 / 100	27 ms	6824 KiB

molecules

#include "molecules.h"
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

vector<int> find_subset(int minn, int maks, vector<int> w) {
    int n=w.size();
    vector<pair<int,int>> vv(n);
    for(int i=0;i<n;i++){
		vv[i]=make_pair(w[i],i);
	}
	sort(vv.begin(),vv.end());
	
	vector<long long> pref(n+1,0ll);
	vector<long long> suf(n+2,0ll);
	for(int i=1;i<=n;i++){
		pref[i]=pref[i-1]+(long long)vv[i-1].fi;
	}
    for(int i=n;i>=1;i--){
		suf[i]=suf[i+1]+(long long)vv[i-1].fi;
	}
	
	int brbr=-1;
	for(int i=1;i<=n;i++){
		if(pref[i]<=(long long)maks && suf[n+1-i]>=(long long)minn){
			brbr=i;
			break;
		}
	}
	
	vector<int> ans;
	ans.clear();
	if(brbr==-1)return ans;
	
	int l,r;
	for(int i=1;i+brbr-1<=n;i++){
		if(pref[i+brbr-1]-pref[i-1]<=maks && pref[i+brbr-1]-pref[i-1]>=minn){
			l=i;
			r=i+brbr-1;
			break;
		}
	}
	l--;r--;
	for(int i=l;i<=r;i++)ans.push_back(vv[i].second);
	return ans;
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 10 / 10
• 서브태스크 3: 12 / 12
• 서브태스크 4: 15 / 15
• 서브태스크 5: 23 / 23
• 서브태스크 6: 31 / 31