There are n files numbered 1 to n in order, and file i has size wᵢ.
The files are split, in number order, across several backup disks that all have capacity C.
Each disk holds only files with consecutive numbers, and the total size of the files on one disk cannot exceed C.
You cannot change the order of the files or split one file across two disks.
Print the smallest integer C that lets all files fit on at most d disks.
The first line gives n and d, and the second line gives w₁ … wₙ, separated by spaces.
Input
1 ≤ d ≤ n ≤ 10,000, 1 ≤ wᵢ ≤ 10⁹
Output
The smallest capacity C
Example 1 · stdin
6 3
3 2 2 4 1 4
stdout
6
Example 2 · stdin
4 2
1 1 1 10
stdout
10
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Trying C = 1, 2, 3, … may have to go all the way to the total (10¹³). A larger capacity needs fewer disks, so 'does it fit on at most d disks?' is false at the front and true at the back. So binary search the answer: count the disks needed for the middle value mid; if it works set hi = mid, otherwise lo = mid + 1. Counting disks is greedy: put the file on the current disk while it fits, and move to a new disk when it would overflow. That is at most 44 × n steps, which is fast. Three traps: (1) the lower end is the largest file, not 1. Starting at 1, the disk counter puts a file that does not fit onto the disk anyway, giving an answer below 10 for example 2. (2) The total reaches 10¹³, so Java, C#, C and C++ need long/long long. C#'s w.Sum() adds in int and throws OverflowException, so write w.Sum(x => (long)x); C++ std::accumulate needs the start value 0LL to add in long long. Python does not overflow, and JavaScript, TypeScript and Craykon use doubles, which are exact below 2^53 (about 9×10¹⁵). (3) Count disks from 1 — counting from 0 forgets the last disk, the one being filled. Craykon has no integer division, so the middle is Mathf.Quot(lo + hi, 2).
Pythonmain.py · 23 lines
def disks_needed(w, cap): """용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).""" disks, used = 1, 0 for x in w: if used + x > cap: disks += 1 used = 0 used += x return disksn, d = map(int, input().split())w = list(map(int, input().split()))# 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이. '되는가'는 앞쪽이 거짓, 뒤쪽이 참이다.lo, hi = max(w), sum(w)while lo < hi: mid = (lo + hi) // 2 if disks_needed(w, mid) <= d: hi = mid else: lo = mid + 1print(lo)
JavaScriptmain.js · 24 lines
// 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).function disksNeeded(w, cap) { let disks = 1; let used = 0; for (const x of w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks;}const [n, d, ...w] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이. 합은 10¹³까지라 2^53 안이다.let lo = Math.max(...w);let hi = w.reduce((s, x) => s + x, 0);while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1;}console.log(lo);
TypeScriptmain.ts · 26 lines
import { readFileSync } from "node:fs";// 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).function disksNeeded(w: number[], cap: number): number { let disks = 1; let used = 0; for (const x of w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks;}const [n, d, ...w]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이. 합은 10¹³까지라 2^53 안이다.let lo = Math.max(...w);let hi = w.reduce((s, x) => s + x, 0);while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1;}console.log(lo);
JavaMain.java · 41 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { // 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일). static int disksNeeded(int[] w, long cap) { int disks = 1; long used = 0; for (int x : w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int d = Integer.parseInt(st.nextToken()); int[] w = new int[n]; long lo = 0, hi = 0; // 합은 10¹³까지라 long st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { w[i] = Integer.parseInt(st.nextToken()); lo = Math.max(lo, w[i]); hi += w[i]; } while (lo < hi) { long mid = lo + (hi - lo) / 2; if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1; } System.out.println(lo); }}
C#Main.cs · 37 lines
using System;using System.Linq;class Program{ // 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일). static int DisksNeeded(int[] w, long cap) { int disks = 1; long used = 0; foreach (int x in w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks; } static void Main() { int d = int.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[1]); int[] w = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); long lo = w.Max(); long hi = w.Sum(x => (long)x); // w.Sum()은 int로 더하다 OverflowException while (lo < hi) { long mid = lo + (hi - lo) / 2; if (DisksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1; } Console.WriteLine(lo); }}
C++main.cpp · 33 lines
#include <algorithm>#include <iostream>#include <numeric>#include <vector>// 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).int disksNeeded(const std::vector<int>& w, long long cap) { int disks = 1; long long used = 0; for (int x : w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks;}int main() { int n, d; std::cin >> n >> d; std::vector<int> w(n); for (int& x : w) std::cin >> x; long long lo = *std::max_element(w.begin(), w.end()); long long hi = std::accumulate(w.begin(), w.end(), 0LL); // 0이 아니라 0LL: 시작값의 타입으로 더한다 while (lo < hi) { long long mid = lo + (hi - lo) / 2; if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1; } std::cout << lo << "\n";}
Cmain.c · 35 lines
#include <stdio.h>static int w[10000];/* 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일). */static int disks_needed(int n, long long cap) { int disks = 1; long long used = 0; for (int i = 0; i < n; i++) { if (used + w[i] > cap) { disks++; used = 0; } used += w[i]; } return disks;}int main(void) { int n, d; long long lo = 0, hi = 0; /* 합은 10¹³까지라 long long */ scanf("%d %d", &n, &d); for (int i = 0; i < n; i++) { scanf("%d", &w[i]); if (w[i] > lo) lo = w[i]; hi += w[i]; } while (lo < hi) { long long mid = lo + (hi - lo) / 2; if (disks_needed(n, mid) <= d) hi = mid; else lo = mid + 1; } printf("%lld\n", lo); return 0;}
Craykonmain.cray · 41 lines
// 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).필요한디스크(w, cap){ disks = 1; used = 0; foreach (x in w) { if (used + x > cap) { disks += 1; used = 0; } used += x; } return disks;}첫줄 = Console.ReadNumbers();d = 첫줄[1];w = Console.ReadNumbers();// 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이lo = 0;hi = 0;foreach (x in w){ lo = Mathf.Max(lo, x); hi += x;}while (lo < hi){ mid = Mathf.Quot(lo + hi, 2); if (필요한디스크(w, mid) <= d) { hi = mid; } else { lo = mid + 1; }}Console.WriteLine(lo);