oj.uz

답안 #906443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
906443 2024-01-14T09:59:01 Z JakobZorz Hiring (IOI09_hiring) C++17
27 / 100
 1500 ms 12384 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<<opt+1<<"\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]+1<<"\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
12.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 0 ms 344 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Partially correct 1 ms 348 KB Partially correct
5 Partially correct 1 ms 348 KB Partially correct
6 Partially correct 43 ms 348 KB Partially correct
7 Partially correct 48 ms 348 KB Partially correct
8 Partially correct 183 ms 556 KB Partially correct
9 Partially correct 355 ms 592 KB Partially correct
10 Partially correct 354 ms 656 KB Partially correct
11 Partially correct 793 ms 700 KB Partially correct
12 Partially correct 531 ms 744 KB Partially correct
13 Execution timed out 1525 ms 1204 KB Time limit exceeded
14 Execution timed out 1520 ms 1116 KB Time limit exceeded
15 Execution timed out 1600 ms 1168 KB Time limit exceeded

Subtask #2
6.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Execution timed out 1573 ms 1072 KB Time limit exceeded
5 Execution timed out 1602 ms 2364 KB Time limit exceeded
6 Execution timed out 1556 ms 7636 KB Time limit exceeded
7 Execution timed out 1539 ms 10064 KB Time limit exceeded

Subtask #3
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 344 KB Partially correct
2 Partially correct 4 ms 348 KB Partially correct
3 Partially correct 4 ms 348 KB Partially correct

Subtask #4
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 11 ms 344 KB Partially correct
2 Partially correct 11 ms 344 KB Partially correct
3 Partially correct 11 ms 344 KB Partially correct

Subtask #5
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 18 ms 348 KB Partially correct
2 Partially correct 20 ms 348 KB Partially correct
3 Partially correct 17 ms 348 KB Partially correct

Subtask #6
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1538 ms 3560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1524 ms 5464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1529 ms 11136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1536 ms 12384 KB Time limit exceeded
2 Halted 0 ms 0 KB -