oj.uz

Submission #906435

# Submission time Handle Problem Language Result Execution time Memory
906435 2024-01-14T09:42:28 Z JakobZorz Hiring (IOI09_hiring) C++17
2 / 100
 1500 ms 12752 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);
    vector<int>res;
    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].s*arr[i].q;
        if(cost>w*arr[i].q)
            continue;
        int cres=0;
        vector<int>cresv={arr[i].i};
        while(cres<(int)vals.size()){
            if(cost+arr[cres].s*arr[cres].q<=w*arr[i].q){
                cost+=arr[cres].s*arr[cres].q;
                cresv.push_back(arr[cres].i);
                cres++;
            }else{
                break;
            }
        }
        if(cresv.size()>res.size())
            res=cresv;
    }
    cout<<res.size()<<"\n";
    for(int i:res)
        cout<<i<<"\n";
}
 
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
2
3
 
 
3 4
1 2
1 3
1 3
 
3
1
2
3
 
 
3 40
10 1
10 2
10 3
 
2
2
3
 
 */

Subtask #1
2.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Partially correct 0 ms 348 KB Partially correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Incorrect 42 ms 348 KB Output isn't correct
7 Incorrect 62 ms 604 KB Output isn't correct
8 Incorrect 184 ms 624 KB Output isn't correct
9 Incorrect 360 ms 600 KB Output isn't correct
10 Incorrect 362 ms 860 KB Output isn't correct
11 Incorrect 801 ms 1104 KB Output isn't correct
12 Incorrect 568 ms 1096 KB Output isn't correct
13 Execution timed out 1561 ms 1160 KB Time limit exceeded
14 Execution timed out 1531 ms 980 KB Time limit exceeded
15 Execution timed out 1526 ms 1164 KB Time limit exceeded

Subtask #2
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Execution timed out 1565 ms 1188 KB Time limit exceeded
5 Execution timed out 1561 ms 2444 KB Time limit exceeded
6 Execution timed out 1561 ms 8028 KB Time limit exceeded
7 Execution timed out 1567 ms 10280 KB Time limit exceeded

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1562 ms 3484 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 1543 ms 5420 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 1543 ms 11312 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 1529 ms 12752 KB Time limit exceeded
2 Halted 0 ms 0 KB -