oj.uz

Submission #979915

# Submission time Handle Problem Language Result Execution time Memory
979915 2024-05-11T15:57:21 Z SmuggingSpun Rice Hub (IOI11_ricehub) C++14
17 / 100
 226 ms 7344 KB 
#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 1e5 + 5;
int N = 1, ans = 0, cnt[lim], to_X[lim];
map<int, int>X_to;
ll sum[lim];
ll get_value(int p, int range){
	int P = lower_bound(to_X + 1, to_X + N + 1, to_X[p] - range) - to_X - 1;
	ll sum_left = 1LL * to_X[p] * (cnt[p] - cnt[P]) - sum[p] + sum[P];
	P = upper_bound(to_X + 1, to_X + N + 2, to_X[p] + range) - to_X - 1;
	return sum_left + sum[P] - sum[p] - 1LL * to_X[p] * (cnt[P] - cnt[p]);
}
int besthub(int n, int L, int X[], ll B){
	memset(cnt, 0, sizeof(cnt));
	memset(sum, 0, sizeof(sum));
	X_to[to_X[1] = X[0]] = 1;
	for(int i = 0; i < n; i++){
		if(i > 0 && X[i] != X[i - 1]){
			X_to[to_X[++N] = X[i]] = N;
		}
		cnt[N]++;
		sum[N] += X[i];
	}
	for(int i = 1; i <= N; i++){
		cnt[i] += cnt[i - 1];
		sum[i] += sum[i - 1];
	}
	to_X[N + 1] = INT_MAX;
	for(int i = 1; i <= N; i++){
		int low = 0, high = L, range;
		while(low <= high){
			int mid = (low + high) >> 1;
			if(get_value(i, mid) <= B){
				low = (range = mid) + 1;
			}
			else{
				high = mid - 1;
			}
		}
		ll remain = B - get_value(i, range);
		map<int, int>::iterator it = X_to.find(to_X[i] - range - 1);
		int add_cnt = 0; 
		if(it != X_to.end()){
			int can_add = min(ll(cnt[it->second] - cnt[it->second - 1]), remain / (range + 1));
			add_cnt += can_add;
			remain -= 1LL * can_add * range;
		}
		it = X_to.find(to_X[i] + range + 1);
		if(it != X_to.end()){
			add_cnt += min(ll(cnt[it->second] - cnt[it->second - 1]), remain / (range + 1));
		}
		maximize(ans, add_cnt + cnt[upper_bound(to_X + 1, to_X + N + 2, to_X[i] + range) - to_X - 1] - cnt[lower_bound(to_X + 1, to_X + N + 1, to_X[i] - range) - to_X - 1]);
	}
	return ans;
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, ll)':
ricehub.cpp:26:14: warning: operation on 'N' may be undefined [-Wsequence-point]
   26 |    X_to[to_X[++N] = X[i]] = N;
      |              ^~~
ricehub.cpp:26:14: warning: operation on 'N' may be undefined [-Wsequence-point]
ricehub.cpp:48:50: warning: 'range' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |   map<int, int>::iterator it = X_to.find(to_X[i] - range - 1);
      |                                          ~~~~~~~~^~~~~~~

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 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Incorrect 1 ms 2652 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Incorrect 2 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3420 KB Output is correct
2 Correct 38 ms 3416 KB Output is correct
3 Correct 149 ms 7268 KB Output is correct
4 Correct 226 ms 7344 KB Output is correct
5 Correct 5 ms 2904 KB Output is correct
6 Incorrect 5 ms 2908 KB Output isn't correct
7 Halted 0 ms 0 KB -