oj.uz

답안 #906433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
906433 2024-01-14T09:38:45 Z JakobZorz Hiring (IOI09_hiring) C++17
0 / 100
 1500 ms 17692 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].s*arr[i].q;
        if(cost>w*arr[i].q)
            continue;
        int cres=0;
        while(cres<(int)vals.size()){
            if(cost+arr[cres].s*arr[cres].q<=w*arr[i].q){
                cost+=arr[cres].s*arr[cres].q;
                cres++;
            }else{
                break;
            }
        }
        res=max(res,cres+1);
    }
    cout<<res<<"\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
 
 */

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
2 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
3 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
4 Incorrect 1 ms 456 KB Unexpected end of file - int32 expected
5 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
6 Incorrect 45 ms 516 KB Unexpected end of file - int32 expected
7 Incorrect 50 ms 540 KB Unexpected end of file - int32 expected
8 Incorrect 191 ms 576 KB Unexpected end of file - int32 expected
9 Incorrect 363 ms 604 KB Unexpected end of file - int32 expected
10 Incorrect 366 ms 668 KB Unexpected end of file - int32 expected
11 Incorrect 793 ms 768 KB Unexpected end of file - int32 expected
12 Incorrect 509 ms 900 KB Unexpected end of file - int32 expected
13 Execution timed out 1576 ms 1040 KB Time limit exceeded
14 Execution timed out 1570 ms 1036 KB Time limit exceeded
15 Execution timed out 1533 ms 1396 KB Time limit exceeded

Subtask #2
0.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
2 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
3 Incorrect 1 ms 460 KB Unexpected end of file - int32 expected
4 Execution timed out 1587 ms 1424 KB Time limit exceeded
5 Execution timed out 1553 ms 3784 KB Time limit exceeded
6 Execution timed out 1536 ms 11128 KB Time limit exceeded
7 Execution timed out 1594 ms 14156 KB Time limit exceeded

Subtask #3
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

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

Subtask #7
0.0 / 6.0

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

Subtask #8
0.0 / 6.0

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

Subtask #9
0.0 / 6.0

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