이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
#define pirp pair<int,ldb>
using namespace std;
const int maxn = 5e5 + 5;
const int MN = 2e4 + 5;
struct DSA{
int num = 0;ldb cost = 0;
bool operator <(const DSA&other) const{
return (num < other.num) || (num == other.num && cost > other.cost);
}
bool operator >(const DSA&other) const{
return (num > other.num) || (num == other.num && cost < other.cost);
}
};
struct CTDL{
int S = 0,Q = 0;ldb cpr = 0;int id = 0;
bool operator <(const CTDL&other) const{
return (cpr < other.cpr);
}
};
struct segment_tree{
ll seg[4*MN];int cnt[4*maxn];
DSA calc(int l,int r,int v,ldb cap){
if (l == r){
ldb x = l;
//x * y <= cap, y <= cnt[v]
ll y = min((ldb)cap/(ldb)x,(ldb)cnt[v]);
return {(int)y,x * y};
}
int w = (l + r)/2;
if (seg[2*v + 1] >= cap)
return calc(l,w,2*v + 1,cap);
DSA res = {cnt[2*v + 1],(ldb)seg[2*v + 1]};
cap -= seg[2*v + 1];
DSA tmp = calc(w + 1,r,2*v + 2,cap);
res.num += tmp.num;
res.cost += tmp.cost;
return res;
}
void update(int l,int r,int v,int p,int val){
if (l > p || r < p) return;
if (l == r){
cnt[v] += val;
seg[v] = (ll)p * (ll)cnt[v];
return;
}
int w = (l + r)/2;
update(l,w,2*v + 1,p,val);
update(w + 1,r,2*v + 2,p,val);
seg[v] = seg[2*v + 1] + seg[2*v + 2];
cnt[v] = cnt[2*v + 1] + cnt[2*v + 2];
}
} seg;
CTDL a[maxn];
void input(int n){
for (int i = 1 ; i <= n ; i++){
cin >> a[i].S >> a[i].Q;
a[i].cpr = (ldb)a[i].S/a[i].Q;
a[i].id = i;
}
sort(a + 1,a + 1 + n);
}
vector <int> lst;
void TRACE(DSA res,int trace){
vector <pir> vec;
lst.push_back(a[trace].id);
for (int i = 1 ; i < trace ; i++)
vec.push_back({a[i].Q,a[i].id});
sort(vec.begin(),vec.end());
for (int i = 0 ; i < res.num - 1 ; i++)
lst.push_back(vec[i].se);
sort(lst.begin(),lst.end());
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;ll W;
cin >> n >> W;
input(n);
DSA res = {0,(ldb)W};
int N = 0;
for (int i = 1 ; i <= n ; i++) N = max(N,a[i].Q);
int trace = 0;
for (int i = 1 ; i <= n ; i++) if (a[i].S <= W){
ldb cap = (ldb)(W - a[i].S)/(ldb)a[i].cpr;
DSA T = seg.calc(1,N,0,cap);
T.cost *= (ldb)a[i].cpr;
T.cost += (ldb)a[i].S;
T.num++;
if (res < T){
res = T;
trace = i;
}
seg.update(1,N,0,a[i].Q,1);
}
else
seg.update(1,N,0,a[i].Q,1);
TRACE(res,trace);
cout << lst.size() << "\n";
for (int x : lst) cout << x << "\n";
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... |