oj.uz

Submission #998660

# Submission time Handle Problem Language Result Execution time Memory
998660 2024-06-14T12:59:07 Z bachhoangxuan Salesman (IOI09_salesman) C++17
0 / 100
 230 ms 19396 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5+5;
int N,S[maxn],Q[maxn],W;
int sum;
priority_queue<int> pq;

signed main(){
    cin >> N >> W;
    for(int i=1;i<=N;i++) cin >> S[i] >> Q[i];
    vector<int> ord(N);
    iota(ord.begin(),ord.end(),1);
    sort(ord.begin(),ord.end(),[&](int x,int y){
        return S[x]*Q[y]<S[y]*Q[x];
    });
    pair<pair<int,long double>,int> Max={{-1,-1},-1};
    for(int x:ord){
        int mx=(W*Q[x])/S[x];
        pq.push(Q[x]);sum+=Q[x];
        while(sum>mx) sum-=pq.top(),pq.pop();
        Max=max(Max,{{(int)pq.size(),-(long double)sum*S[x]/Q[x]},x});
    }
    cout << Max.first.first << '\n';
    int a=Max.second;
    vector<int> cur;
    for(int x:ord){
        cur.push_back(x);
        if(x==a) break;
    }
    W=(W*Q[a])/S[a];
    sort(cur.begin(),cur.end(),[&](int x,int y){
        return Q[x]<Q[y];
    });
    for(int x:cur){
        W-=Q[x];
        if(W<0) break;
        cout << x << '\n';
    }
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Incorrect 2 ms 2396 KB Output isn't correct
6 Incorrect 9 ms 3164 KB Output isn't correct
7 Incorrect 24 ms 7892 KB Output isn't correct
8 Incorrect 47 ms 8788 KB Output isn't correct
9 Incorrect 63 ms 9556 KB Output isn't correct
10 Incorrect 126 ms 12368 KB Output isn't correct
11 Incorrect 139 ms 13004 KB Output isn't correct
12 Incorrect 174 ms 14804 KB Output isn't correct
13 Incorrect 176 ms 14884 KB Output isn't correct
14 Incorrect 227 ms 18260 KB Output isn't correct
15 Incorrect 220 ms 17484 KB Output isn't correct
16 Incorrect 225 ms 17748 KB Output isn't correct
17 Incorrect 1 ms 2396 KB Output isn't correct
18 Incorrect 0 ms 2396 KB Output isn't correct
19 Incorrect 1 ms 2396 KB Output isn't correct
20 Incorrect 1 ms 2396 KB Output isn't correct
21 Incorrect 1 ms 2396 KB Output isn't correct
22 Incorrect 2 ms 2396 KB Output isn't correct
23 Incorrect 3 ms 2396 KB Output isn't correct
24 Incorrect 2 ms 2396 KB Output isn't correct
25 Incorrect 41 ms 8652 KB Output isn't correct
26 Incorrect 86 ms 10924 KB Output isn't correct
27 Incorrect 132 ms 13008 KB Output isn't correct
28 Incorrect 148 ms 13400 KB Output isn't correct
29 Incorrect 221 ms 18888 KB Output isn't correct
30 Incorrect 230 ms 19396 KB Output isn't correct