Submission #229211

#	Time	Username	Problem	Language	Result	Execution time	Memory
229211		tushar_2658	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	1093 ms	4712 KiB

molecules

#include "molecules.h"
#include "bits/stdc++.h"
using namespace std;

using ll = long long;

std::vector<int> find_subset(int l, int u, std::vector<int> w) {
	int N = w.size();
  vector<pair<int, int>> a;
  for(int i = 0; i < N; ++i){
    a.push_back(make_pair(w[i], i));
  }
  sort(a.begin(), a.end());
  ll taken = 0;
  vector<int> v;
  vector<ll> pref(N + 1);
  for(int i = 0; i < N; ++i){
    if(i == 0){
      pref[i] = a[i].first;
    }else {
      pref[i] = pref[i - 1] + a[i].first;
    }
  }
  bool good = 0;
  for(int len = 1; len <= N; ++len){
    for(int i = 0; i + len - 1 < N; ++i){
      int r = i + len - 1;
      ll sum = 0;
      if(i != 0){
        sum = pref[r] - pref[i - 1];
      }else {
        sum = pref[r];
      }
      if(sum >= l && sum <= u){
        good = 1;
        for(int j = i; j <= r; ++j){
          v.push_back(a[j].second);
        }
        break;
      }
    }
    if(good){
      break;
    }
  }
  sort(v.begin(), v.end());
  return v;
}

Compilation message (stderr)

molecules.cpp: In function 'std::vector<int> find_subset(int, int, std::vector<int>)':
molecules.cpp:14:6: warning: unused variable 'taken' [-Wunused-variable]
   ll taken = 0;
      ^~~~~

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