oj.uz

답안 #906441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
906441 2024-01-14T09:55:56 Z JakobZorz Hiring (IOI09_hiring) C++17
27 / 100
 1500 ms 12784 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;
    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;
            }
        }
        res=max(res,cres+1);
    }
    cout<<res<<"\n";
    for(int i=0;i<res;i++)
        cout<<"0\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
 
 
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 1 ms 348 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Partially correct 0 ms 348 KB Partially correct
5 Partially correct 1 ms 344 KB Partially correct
6 Partially correct 41 ms 348 KB Partially correct
7 Partially correct 58 ms 516 KB Partially correct
8 Partially correct 184 ms 568 KB Partially correct
9 Partially correct 362 ms 592 KB Partially correct
10 Partially correct 352 ms 596 KB Partially correct
11 Partially correct 795 ms 700 KB Partially correct
12 Partially correct 555 ms 764 KB Partially correct
13 Execution timed out 1552 ms 768 KB Time limit exceeded
14 Execution timed out 1536 ms 860 KB Time limit exceeded
15 Execution timed out 1556 ms 1176 KB Time limit exceeded

Subtask #2
6.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 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 1076 KB Time limit exceeded
5 Execution timed out 1531 ms 2500 KB Time limit exceeded
6 Execution timed out 1571 ms 7680 KB Time limit exceeded
7 Execution timed out 1554 ms 10156 KB Time limit exceeded

Subtask #3
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 3 ms 348 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 492 KB Partially correct
2 Partially correct 11 ms 348 KB Partially correct
3 Partially correct 11 ms 348 KB Partially correct

Subtask #5
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 19 ms 600 KB Partially correct
2 Partially correct 18 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 1528 ms 3504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

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

Subtask #8
0.0 / 6.0

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

Subtask #9
0.0 / 6.0

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