oj.uz

Submission #655639

# Submission time Handle Problem Language Result Execution time Memory
655639 2022-11-05T04:12:42 Z horiseun Rice Hub (IOI11_ricehub) C++11
0 / 100
 1000 ms 41884 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
#define ll long long

vector<ll> pref;
 
ll calc(int length, int x[], int r) {
	ll val = LLONG_MAX;
	for (int i = length - 1; i < r; i++) {
		int start = i - length + 1;
		int pos = (i + i - length + 1) / 2;
		val = min(val, (pos - start) * x[pos] - (pref[pos] - pref[start]) + (pref[i + 1] - pref[pos + 1]) - (i - pos) * x[pos]);
	}
	return val;
}
 
int besthub(int r, int l, int x[], ll b) {
	pref.push_back(0);
	for (int i = 0; i < r; i++) {
		pref.push_back(pref[i] + x[i]);
	}
 
	int low = 0, upp = r + 1;
	while (low + 1 != upp) {
		int mid = (low + upp) / 2;
		if (calc(mid, x, r) <= b) low = mid;
		else upp = mid;
	}
 
	cout << low << "\n";
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:35:1: warning: no return statement in function returning non-void [-Wreturn-type]
   35 | }
      | ^

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 41884 KB Time limit exceeded
2 Halted 0 ms 0 KB -