mirror of
https://github.com/Luzifer/codingame-solutions.git
synced 2024-09-18 23:23:00 +00:00
77 lines
1.3 KiB
Go
77 lines
1.3 KiB
Go
package main
|
|
|
|
import (
|
|
"bufio"
|
|
"fmt"
|
|
"log"
|
|
"os"
|
|
"time"
|
|
)
|
|
|
|
type calculationResult struct{ Seated, Next int }
|
|
|
|
var (
|
|
groups [1000]int
|
|
calculationCache = map[int]calculationResult{}
|
|
)
|
|
|
|
func main() {
|
|
defer timeTrack(time.Now(), "main")
|
|
scanner := bufio.NewScanner(os.Stdin)
|
|
scanner.Buffer(make([]byte, 1000000), 1000000)
|
|
scanner.Split(bufio.ScanWords)
|
|
|
|
var L, C, N, i int
|
|
scanner.Scan()
|
|
L = toInt(scanner.Bytes())
|
|
scanner.Scan()
|
|
C = toInt(scanner.Bytes())
|
|
scanner.Scan()
|
|
N = toInt(scanner.Bytes())
|
|
|
|
log.Printf("C: %d", C)
|
|
|
|
for ; i < N; i++ {
|
|
scanner.Scan()
|
|
groups[i] = toInt(scanner.Bytes())
|
|
}
|
|
|
|
var earned, next, seated, j int
|
|
for i = 0; i < C; i++ {
|
|
key := next
|
|
seated = 0
|
|
|
|
if cr, ok := calculationCache[key]; ok {
|
|
seated = cr.Seated
|
|
next = cr.Next
|
|
} else {
|
|
j = 0
|
|
for j < N && groups[next] <= L-seated {
|
|
seated += groups[next]
|
|
j++
|
|
next++
|
|
if next == N {
|
|
next = 0
|
|
}
|
|
}
|
|
calculationCache[key] = calculationResult{Seated: seated, Next: next}
|
|
}
|
|
|
|
earned += seated
|
|
}
|
|
|
|
fmt.Printf("%d\n", earned)
|
|
}
|
|
|
|
func toInt(buf []byte) (n int) {
|
|
for _, v := range buf {
|
|
n = n*10 + int(v-'0')
|
|
}
|
|
return
|
|
}
|
|
|
|
func timeTrack(start time.Time, name string) {
|
|
elapsed := time.Since(start)
|
|
log.Printf("%s took %s", name, elapsed)
|
|
}
|