# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
892646 |
2023-12-25T16:05:13 Z |
Macker |
Hiring (IOI09_hiring) |
C++17 |
|
426 ms |
23724 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
struct node {
int cnt = 0; ld val = 0;
};
const int len = 32768;
vector<node> st(len * 2);
void add(int idx, ld val, int i = 1, int s = 0, int e = len){
if(idx >= e || idx < s) return;
if(idx == s && s + 1 == e) {
st[i].val += val;
st[i].cnt++;
return;
}
add(idx, val, i * 2, s, (s + e) / 2);
add(idx, val, i * 2 + 1, (s + e) / 2, e);
st[i].val = st[i * 2].val + st[i * 2 + 1].val;
st[i].cnt = st[i * 2].cnt + st[i * 2 + 1].cnt;
}
int walk(ld b, ld m, int i = 1){
if(i >= len){
if(st[i].val * m <= b) return st[i].cnt;
else return 0;
}
if(st[i * 2].val * m <= b) return st[i * 2].cnt + walk(b - st[i * 2].val * m, m, i * 2 + 1);
else return walk(b, m, i * 2);
}
int main()
{
int n, b; cin >> n >> b;
vector<pair<ld, int>> v;
for (int i = 0; i < n; i++) {
int c, q; cin >> c >> q;
v.push_back({(ld)c / (ld)q, q});
}
sort(all(v));
int mx = 0, mxi;
for (int i = 0; i < n; i++) {
auto& [x, q] = v[i];
add(q, q);
int ret = walk(b, x);
if(ret > mx){
mx = ret;
mxi = i;
}
}
cout << mx << endl;
}
Compilation message
hiring.cpp: In function 'int main()':
hiring.cpp:50:17: warning: variable 'mxi' set but not used [-Wunused-but-set-variable]
50 | int mx = 0, mxi;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
2396 KB |
Unexpected end of file - int32 expected |
2 |
Incorrect |
2 ms |
2396 KB |
Unexpected end of file - int32 expected |
3 |
Incorrect |
1 ms |
2460 KB |
Unexpected end of file - int32 expected |
4 |
Incorrect |
2 ms |
2396 KB |
Unexpected end of file - int32 expected |
5 |
Incorrect |
2 ms |
2396 KB |
Unexpected end of file - int32 expected |
6 |
Incorrect |
3 ms |
2632 KB |
Unexpected end of file - int32 expected |
7 |
Incorrect |
3 ms |
2652 KB |
Unexpected end of file - int32 expected |
8 |
Incorrect |
4 ms |
2652 KB |
Unexpected end of file - int32 expected |
9 |
Incorrect |
7 ms |
2904 KB |
Unexpected end of file - int32 expected |
10 |
Incorrect |
5 ms |
3160 KB |
Unexpected end of file - int32 expected |
11 |
Incorrect |
10 ms |
2908 KB |
Unexpected end of file - int32 expected |
12 |
Incorrect |
10 ms |
2904 KB |
Unexpected end of file - int32 expected |
13 |
Incorrect |
9 ms |
3028 KB |
Unexpected end of file - int32 expected |
14 |
Incorrect |
18 ms |
3028 KB |
Unexpected end of file - int32 expected |
15 |
Incorrect |
15 ms |
3288 KB |
Unexpected end of file - int32 expected |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2396 KB |
Unexpected end of file - int32 expected |
2 |
Incorrect |
2 ms |
2392 KB |
Unexpected end of file - int32 expected |
3 |
Incorrect |
2 ms |
2396 KB |
Unexpected end of file - int32 expected |
4 |
Incorrect |
17 ms |
3744 KB |
Unexpected end of file - int32 expected |
5 |
Incorrect |
44 ms |
8076 KB |
Unexpected end of file - int32 expected |
6 |
Incorrect |
248 ms |
22468 KB |
Unexpected end of file - int32 expected |
7 |
Incorrect |
286 ms |
22152 KB |
Unexpected end of file - int32 expected |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2652 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2396 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
2396 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
97 ms |
8640 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
149 ms |
13248 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
335 ms |
22524 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
426 ms |
23724 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |