Submission #1033664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033664		pdao	Stove (JOI18_stove)	C++14	0 / 100	0 ms	348 KiB

stove

#include <bits/stdc++.h> 
using namespace std; 

bool check(int mid, int a[], int n, int k) { 
	int count = 0; 
	int sum = 0; 
	for (int i = 0; i < n; i++) { 
		if (a[i] > mid) 
			return false; 

		sum += a[i]; 
		if (sum > mid) { 
			count++; 
			sum = a[i]; 
		} 
	} 
	count++; 

	if (count <= k) 
		return true; 
	return false; 
} 

int solve (int a[], int n, int k) { 
	int* max = max_element(a, a + n); 
	int l = *max; 
	int r = 0; 

	for (int i = 0; i < n; i++) { 
		r += a[i];
	} 

	int ans = 0; 
	while (l <= r) { 
		int mid = (l + r) / 2; 
    
		if (check(mid, a, n, k)) { 
			ans = mid; 
			r = mid - 1; 
		} 

		else { 
			l = mid + 1; 
		} 
	} 

	return ans; 
} 

int main() { 
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  int a[n];
  for (int i = 0; i < n; i++) cin >> a[i];
    
  int distances[n - 1];
    
  for (int i = 1; i < n; i++)
    distances[i - 1] = a[i] - a[i - 1];
    
	cout << solve(distances, n - 1, k) + 1; 
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50