Submission #556809


Source Code Expand

package main
import (
	"fmt"
	"io"
	"bufio"
	"os"
	"strconv"
	"math"
	"sort"
)

func main() {
	n := nextInt()

	bl := make([][]int, n)
	time := make([]int, n)
	for i := range bl {
		bl[i] = make([]int, 2)
		bl[i][0] = nextInt()
		bl[i][1] = nextInt()
	}

	min := 0
	max := int(math.Pow10(16))
	for i := range bl {
		if min < bl[i][0] {
			min = bl[i][0]
		}
	}
	min -= 1
	for max - min > 1 {
		med := (max + min) / 2
		if isOK(med, bl, time) {
			max = med
		} else {
			min = med
		}
	}
	fmt.Println(max)
}

func isOK(max int, bal [][]int, time []int) bool {
	n := len(bal)
	for i := 0 ; i < n ; i++ {
		time[i] = (max - bal[i][0]) / bal[i][1]
	}
	sort.Ints(time)
	for i := 0 ; i < n ; i++ {
		if time[i] < i {
			return false
		}
	}
	return true
}

// ------------------


var rdr = bufio.NewReader(os.Stdin)

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

func nextString(limit int) string {
	return readToken(limit)
}

func readToken(limit int) string {
	buf := make([]byte, 0, limit)

	for {
		byte, err := rdr.ReadByte()
		if err != nil {
			if err == io.EOF {
				break
			}
		}
		if byte != 10 && byte != 13 && byte != 32 {
			buf = append(buf, byte)
			break
		}
	}
	for {
		byte, err := rdr.ReadByte()
		if err != nil {
			if err == io.EOF {
				break
			}
		}
		if byte == 10 || byte == 13 || byte == 32 {
			break
		}
		buf = append(buf, byte)
	}
	return string(buf)
}

Submission Info

Submission Time
Task D - 射撃王
User hamadu
Language Go (1.4.1)
Score 100
Code Size 1535 Byte
Status AC
Exec Time 2850 ms
Memory 9512 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 2
AC × 17
AC × 32
Set Name Test Cases
Sample subtask0-sample01.txt, subtask0-sample02.txt
Subtask1 subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt
Subtask2 subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt
Case Name Status Exec Time Memory
subtask0-sample01.txt AC 28 ms 1064 KB
subtask0-sample02.txt AC 25 ms 1056 KB
subtask1-01.txt AC 27 ms 1044 KB
subtask1-02.txt AC 26 ms 1176 KB
subtask1-03.txt AC 24 ms 1176 KB
subtask1-04.txt AC 24 ms 940 KB
subtask1-05.txt AC 27 ms 1072 KB
subtask1-06.txt AC 26 ms 1112 KB
subtask1-07.txt AC 25 ms 1176 KB
subtask1-08.txt AC 25 ms 1180 KB
subtask1-09.txt AC 25 ms 1172 KB
subtask1-10.txt AC 26 ms 1048 KB
subtask1-11.txt AC 27 ms 1180 KB
subtask1-12.txt AC 27 ms 1060 KB
subtask1-13.txt AC 27 ms 1180 KB
subtask1-14.txt AC 26 ms 1048 KB
subtask1-15.txt AC 25 ms 928 KB
subtask2-01.txt AC 30 ms 1180 KB
subtask2-02.txt AC 52 ms 1176 KB
subtask2-03.txt AC 100 ms 1316 KB
subtask2-04.txt AC 516 ms 2852 KB
subtask2-05.txt AC 1319 ms 5280 KB
subtask2-06.txt AC 2127 ms 7956 KB
subtask2-07.txt AC 2477 ms 8480 KB
subtask2-08.txt AC 2850 ms 9316 KB
subtask2-09.txt AC 2808 ms 9384 KB
subtask2-10.txt AC 2439 ms 9252 KB
subtask2-11.txt AC 491 ms 9256 KB
subtask2-12.txt AC 2835 ms 9376 KB
subtask2-13.txt AC 2771 ms 9512 KB
subtask2-14.txt AC 2839 ms 9256 KB
subtask2-15.txt AC 2796 ms 9348 KB