oj.uz

Submission #906444

# Submission time Handle Problem Language Result Execution time Memory
906444 2024-01-14T10:01:06 Z JakobZorz Hiring (IOI09_hiring) C++17
28 / 100
 1500 ms 12836 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second
 
struct Obj{
    ll s; // min salary
    ll q; // skill
    int i;
};
 
bool cmp(Obj&a,Obj&b){
    return a.s*b.q<b.s*a.q;
}
 
void solve(){
    int n;
    ll w;
    cin>>n>>w;
    vector<Obj>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i].s>>arr[i].q;
        arr[i].i=i+1;
    }
    sort(arr.begin(),arr.end(),cmp);
    int res=0;
    int opt=0;
    for(int i=0;i<n;i++){
        vector<ll>vals;
        for(int j=0;j<i;j++)
            vals.push_back(arr[j].q);
        sort(vals.begin(),vals.end());
        ll cost=arr[i].q;
        if(cost*arr[i].s>w*arr[i].q)
            continue;
        int cres=0;
        while(cres<(int)vals.size()){
            if((cost+vals[cres])*arr[i].s<=w*arr[i].q){
                cost+=vals[cres];
                cres++;
            }else{
                break;
            }
        }
        if(cres+1>res){
            res=cres+1;
            opt=i;
        }
    }
    cout<<res<<"\n";
    if(res){
        cout<<arr[opt].i<<"\n";
        int i=opt;
        vector<ll>vals;
        vector<int>idx;
        for(int j=0;j<i;j++){
            vals.push_back(arr[j].q);
            idx.push_back(arr[j].i);
        }
        sort(vals.begin(),vals.end());
        ll cost=arr[i].q;
        int cres=0;
        while(cres<(int)vals.size()){
            if((cost+vals[cres])*arr[i].s<=w*arr[i].q){
                cost+=vals[cres];
                cout<<idx[cres]<<"\n";
                cres++;
            }else{
                break;
            }
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}
 
/*
 
4 100
5 1000
10 100
8 10
20 1
 
2
 
 
3 4
1 2
1 3
1 3
 
3
 
 
3 40
10 1
10 2
10 3
 
2
 
 
5 30
1 1
2 2
4 4
8 8
16 16
 
4
 

 */

Subtask #1
13.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Correct 0 ms 348 KB Output is correct
4 Partially correct 1 ms 348 KB Partially correct
5 Partially correct 0 ms 348 KB Partially correct
6 Partially correct 41 ms 524 KB Partially correct
7 Partially correct 49 ms 592 KB Partially correct
8 Partially correct 189 ms 560 KB Partially correct
9 Partially correct 366 ms 828 KB Partially correct
10 Partially correct 351 ms 612 KB Partially correct
11 Partially correct 788 ms 692 KB Partially correct
12 Partially correct 536 ms 748 KB Partially correct
13 Execution timed out 1548 ms 768 KB Time limit exceeded
14 Execution timed out 1523 ms 872 KB Time limit exceeded
15 Execution timed out 1562 ms 996 KB Time limit exceeded

Subtask #2
6.0 / 28.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 1 ms 344 KB Partially correct
3 Partially correct 1 ms 344 KB Partially correct
4 Execution timed out 1545 ms 1280 KB Time limit exceeded
5 Execution timed out 1557 ms 2420 KB Time limit exceeded
6 Execution timed out 1521 ms 7748 KB Time limit exceeded
7 Execution timed out 1508 ms 10164 KB Time limit exceeded

Subtask #3
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 348 KB Partially correct
2 Partially correct 4 ms 348 KB Partially correct
3 Partially correct 3 ms 344 KB Partially correct

Subtask #4
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 348 KB Partially correct
2 Partially correct 11 ms 484 KB Partially correct
3 Partially correct 11 ms 600 KB Partially correct

Subtask #5
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 18 ms 496 KB Partially correct
2 Partially correct 19 ms 344 KB Partially correct
3 Partially correct 17 ms 344 KB Partially correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1518 ms 3408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1525 ms 5200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1540 ms 11280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1549 ms 12836 KB Time limit exceeded
2 Halted 0 ms 0 KB -