제출 #465199

#제출 시각아이디문제언어결과실행 시간메모리
465199dattranxxxDetecting Molecules (IOI16_molecules)C++11
19 / 100
623 ms65540 KiB
/* * Author : shora */ #include <bits/stdc++.h> #define print(_v) for (auto &_ : _v) {cerr << _ << ' ';} cerr << endl; #include "molecules.h" using namespace std; using ll = long long; const int oo = 1e9; const int N = 2e5; map<int, ll> dp[N]; int n; ll call(int i, int l, vector<int>& a) { if (i == -1) return l <= 0 ? 0 : oo; if (dp[i].count(l)) return dp[i][l]; return dp[i][l] = min(call(i-1, l-a[i], a) + a[i], call(i-1, l, a)); } vector<int> find_subset(int l, int u, vector<int> a) { n = a.size(); vector<int> res; call(n-1, l, a); if (dp[n-1][l] > u) return res; int i = n-1; while (~i) { if (call(i-1, l-a[i], a) + a[i] < call(i-1, l, a)) { res.push_back(i); l -= a[i]; } i--; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...