oj.uz

답안 #979904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
979904 2024-05-11T15:30:43 Z SmuggingSpun 쌀 창고 (IOI11_ricehub) C++14
0 / 100
 3 ms 2652 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 cnt[lim], to_X[lim];
ll sum[lim];
int besthub(int n, int L, int X[], ll B){
	int N = 1, ans = 0;
	memset(cnt, 0, sizeof(cnt));
	memset(sum, 0, sizeof(sum));
	to_X[1] = X[0];
	for(int i = 0; i < n; i++){
		if(i > 0 && X[i] != X[i - 1]){
			to_X[++N] = X[i];
		}
		cnt[N]++;
		sum[N] += X[i];
	}
	for(int i = 1; i <= N; i++){
		cnt[i] += cnt[i - 1];
		sum[i] += sum[i - 1];
	}
	for(int i = 1; i <= N; i++){
		int low = 0, high = N, range;
		while(low <= high){
			int mid = (low + high) >> 1;
			if(1LL * to_X[i] * ((cnt[i] << 1) - cnt[max(0, i - mid - 1)] - cnt[min(N, i + mid)]) - (sum[i] << 1LL) + sum[max(0, i - mid - 1)] + sum[min(N, i + mid)] <= B){
				low = (range = mid) + 1;
			}
			else{
				high = mid - 1;
			}
		}
		ll remain = B - 1LL * to_X[i] * ((cnt[i] << 1) + cnt[max(0, i - range - 1)] + cnt[min(N, i + range)]) + (sum[i] << 1LL) - sum[max(0, i - range - 1)] - sum[min(N, i + range)];
		int add_cnt = 0;
		if(i - range > 1){
			int can_add = min(ll(cnt[i - range - 1]) - cnt[i - range - 2], remain / (to_X[i] - to_X[i - range - 1]));
			add_cnt += can_add;
			remain -= 1LL * can_add * (to_X[i] - to_X[i - range - 1]);
		}
		if(i + range < N){
			add_cnt += min(ll(cnt[i + range + 1]) - cnt[i + range], remain / (to_X[i + range + 1] - to_X[i]));
		}
		maximize(ans, add_cnt + cnt[min(N, i + range)] - cnt[max(0, i - range - 1)]);
	}
	return ans;
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, ll)':
ricehub.cpp:40:94: warning: 'range' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |   ll remain = B - 1LL * to_X[i] * ((cnt[i] << 1) + cnt[max(0, i - range - 1)] + cnt[min(N, i + range)]) + (sum[i] << 1LL) - sum[max(0, i - range - 1)] - sum[min(N, i + range)];
      |                                                                                            ~~^~~~~~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -