이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define db double
#define pp pair<db, db>
#define ppp pair<db, pp>
int n; db w;
vector<db> sk;
vector<db> q;
vector<pair<db, int> > v;
multiset<pair<db, int> > s;
int siz = 0;
vector<int> sol;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> w;
sk.resize(n); q.resize(n);
for (int i = 0; i < n; ++i){
cin >> sk[i] >> q[i];
v.push_back({sk[i] / q[i], i});
}
sort(v.begin(), v.end()); db sum = 0;
for (int i = 0; i < n; ++i){
s.insert({q[v[i].S], v[i].S}); sum += q[v[i].S];
while (!s.empty() && sum * v[i].F > w){
auto it = s.end(); --it;
sum -= (*it).F; s.erase(it);
}
siz = max(siz, (int)(s.size()));
}
cout << siz << '\n'; s.clear(); sum = 0;
/*for (int i = 0; i < n; ++i){
s.insert({q[v[i].S], v[i].S}); sum += q[v[i].S];
while (!s.empty() && sum * v[i].F > w){
auto it = s.end(); --it;
sum -= (*it).F; s.erase(it);
}
if (siz == (int)(s.size())){
for (auto x: s)
cout << (x.S + 1);
break;
}
}*/
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |