Submission #7340805


Source Code Expand

Copy
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextInt64() int64 {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func judge(k int64, n int, a int, b int, h []int) bool {
	var sum int64 = 0
	for i := 0; i < n; i++ {
		var t int64 = int64(h[i]) - k*int64(b)
		if t > 0 {
			sum += (t + int64(a-b-1)) / int64(a-b)
			if sum > k {
				return false
			}
		}
	}
	return true
}

func main() {
	sc.Split(bufio.ScanWords)
	var n, a, b int

	n = nextInt()
	a = nextInt()
	b = nextInt()

	h := make([]int, n)

	for i := 0; i < n; i++ {
		h[i] = nextInt()
	}

	var low, high int64 = 0, 1000000009

	for low < high {
		mid := (low + high) / 2
		if judge(mid, n, a, b, h) {
			high = mid
		} else {
			low = mid + 1
		}
	}

	fmt.Println(low)
}

Submission Info

Submission Time
Task D - Widespread
User kira924age
Language Go (1.6)
Score 400
Code Size 1011 Byte
Status
Exec Time 53 ms
Memory 3072 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 400 / 400 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13
Case Name Status Exec Time Memory
a01 1 ms 640 KB
a02 1 ms 640 KB
a03 1 ms 640 KB
b04 1 ms 640 KB
b05 31 ms 3072 KB
b06 50 ms 3072 KB
b07 43 ms 3072 KB
b08 41 ms 3072 KB
b09 28 ms 2944 KB
b10 28 ms 2944 KB
b11 30 ms 2944 KB
b12 30 ms 2944 KB
b13 53 ms 2944 KB