oj.uz

Submission #906436

# Submission time Handle Problem Language Result Execution time Memory
906436 2024-01-14T09:44:03 Z JakobZorz Hiring (IOI09_hiring) C++17
2 / 100
 1500 ms 12828 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";
    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
 
 */

Subtask #1
2.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Partially correct 1 ms 348 KB Partially correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 41 ms 348 KB Output isn't correct
7 Incorrect 49 ms 344 KB Output isn't correct
8 Incorrect 183 ms 348 KB Output isn't correct
9 Incorrect 352 ms 592 KB Output isn't correct
10 Incorrect 374 ms 848 KB Output isn't correct
11 Incorrect 783 ms 640 KB Output isn't correct
12 Incorrect 500 ms 600 KB Output isn't correct
13 Execution timed out 1566 ms 1024 KB Time limit exceeded
14 Execution timed out 1543 ms 1148 KB Time limit exceeded
15 Execution timed out 1548 ms 1100 KB Time limit exceeded

Subtask #2
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Execution timed out 1556 ms 1092 KB Time limit exceeded
5 Execution timed out 1524 ms 2592 KB Time limit exceeded
6 Execution timed out 1559 ms 7684 KB Time limit exceeded
7 Execution timed out 1536 ms 9936 KB Time limit exceeded

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 19 ms 348 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 1528 ms 3304 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 1548 ms 5716 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 1524 ms 11284 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 1509 ms 12828 KB Time limit exceeded
2 Halted 0 ms 0 KB -