oj.uz

Submission #893125

# Submission time Handle Problem Language Result Execution time Memory
893125 2023-12-26T14:31:33 Z AgentPengin Rice Hub (IOI11_ricehub) C++14
100 / 100
 14 ms 3676 KB 
/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 1e5 + 5;

int n,x[MAXN],max_len;
ll b,px[MAXN];

bool check(int mid) {
	for (int L = 1;L + mid - 1 <= n;L++) {
		int R = L + mid - 1;
		int tv = (L + R) >> 1;
		ll cost = (ll)x[tv] * ((ll)tv - L + 1) - (px[tv] - px[L - 1]);
		cost += (px[R] - px[tv]) - x[tv] * (R - (ll)tv);
		if (cost <= b) return true;
	}
	return false;
}

int besthub(int R,int L,int X[],ll B) {
	n = R,max_len = L,b = B;
    for (int i = 1;i <= n;i++) x[i] = X[i - 1];
    sort(x + 1,x + n + 1);
    for (int i = 1;i <= n;i++) px[i] = px[i - 1] + (ll)x[i];
    int l = 2,r = n,ans = 1;
    while(l <= r) {
    	int mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return ans;
}

// signed main() {
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // if (ifstream(NAME".inp")) {
        // freopen(NAME".inp","r",stdin);
        // freopen(NAME".out","w",stdout);
    // }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    // return 0;
// }
// // agent pengin wants to take apio (with anya-san)

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2496 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2508 KB Output is correct
22 Correct 1 ms 2592 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2504 KB Output is correct
25 Correct 1 ms 2536 KB Output is correct
26 Correct 1 ms 2536 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 11 ms 3676 KB Output is correct
4 Correct 11 ms 3676 KB Output is correct
5 Correct 6 ms 2908 KB Output is correct
6 Correct 6 ms 2904 KB Output is correct
7 Correct 9 ms 3416 KB Output is correct
8 Correct 12 ms 3420 KB Output is correct
9 Correct 6 ms 2908 KB Output is correct
10 Correct 5 ms 2908 KB Output is correct
11 Correct 10 ms 3676 KB Output is correct
12 Correct 10 ms 3504 KB Output is correct
13 Correct 6 ms 2908 KB Output is correct
14 Correct 6 ms 2884 KB Output is correct
15 Correct 8 ms 3420 KB Output is correct
16 Correct 8 ms 3280 KB Output is correct
17 Correct 14 ms 3420 KB Output is correct
18 Correct 9 ms 3420 KB Output is correct
19 Correct 9 ms 3556 KB Output is correct
20 Correct 10 ms 3672 KB Output is correct