oj.uz

Submission #1033639

# Submission time Handle Problem Language Result Execution time Memory
1033639 2024-07-25T04:08:03 Z vjudge1 Stove (JOI18_stove) C++17
0 / 100
 1 ms 348 KB 
#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.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 50.0

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