結果

問題 No.527 ナップサック容量問題
ユーザー yuki2006
提出日時 2017-06-09 23:39:01
言語 Go
(1.23.4)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 2,696 bytes
コンパイル時間 14,848 ms
コンパイル使用メモリ 227,600 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 19:23:12
合計ジャッジ時間 16,291 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func main() {
sc := NewScanner()
N := sc.NextInt()
v := make([]int, N)
w := make([]int, N)
for i := 0; i < N; i++ {
v[i] = sc.NextInt()
w[i] = sc.NextInt()
}
V := sc.NextInt()
INF := int(1e8)
dp := make([]int, 100000+1)
for i := 0; i < len(dp); i++ {
dp[i] = INF
}
dp[0] = 0
for i := 0; i < N; i++ {
for k := 100000; k >= v[i]; k-- {
if dp[k-v[i]] == INF {
continue
}
dp[k] = min(dp[k], dp[k-v[i]]+w[i])
}
}
mn := dp[V]
if mn == 0 {
mn = 1
}
fmt.Println(mn)
mx := INF
for i := V + 1; i < len(dp); i++ {
if dp[i] < INF {
mx = min(mx, dp[i])
}
}
if mx == INF {
fmt.Println("inf")
} else {
fmt.Println(mx - 1)
}
}
func max(a int, b int) int {
if a < b {
return b
}
return a
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
type Scanner struct {
r *bufio.Reader
buf []byte
p int
}
func NewScanner() *Scanner {
rdr := bufio.NewReaderSize(os.Stdin, 1000)
return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
s.pre()
start := s.p
for ; s.p < len(s.buf); s.p++ {
if s.buf[s.p] == ' ' {
break
}
}
result := string(s.buf[start:s.p])
s.p++
return result
}
func (s *Scanner) NextLine() string {
s.pre()
start := s.p
s.p = len(s.buf)
return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
v, _ := strconv.Atoi(s.Next())
return v
}
func (s *Scanner) NextInt64() int64 {
v, _ := strconv.ParseInt(s.Next(), 10, 64)
return v
}
func (s *Scanner) NextIntArray() []int {
s.pre()
start := s.p
result := []int{}
for ; s.p < len(s.buf)+1; s.p++ {
if s.p == len(s.buf) || s.buf[s.p] == ' ' {
v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
result = append(result, int(v))
start = s.p + 1
}
}
return result
}
func (s *Scanner) NextInt64Array() []int64 {
s.pre()
start := s.p
result := []int64{}
for ; s.p < len(s.buf)+1; s.p++ {
if s.p == len(s.buf) || s.buf[s.p] == ' ' {
v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
result = append(result, v)
start = s.p + 1
}
}
return result
}
func (s *Scanner) NextMap() map[int]bool {
s.pre()
start := s.p
mp := map[int]bool{}
for ; s.p < len(s.buf); s.p++ {
if s.buf[s.p] == ' ' {
v, _ := strconv.Atoi(string(s.buf[start:s.p]))
mp[v] = true
start = s.p + 1
}
}
v, _ := strconv.Atoi(string(s.buf[start:s.p]))
mp[v] = true
return mp
}
func (s *Scanner) pre() {
if s.p >= len(s.buf) {
s.readLine()
s.p = 0
}
}
func (s *Scanner) readLine() {
s.buf = make([]byte, 0)
for {
l, p, e := s.r.ReadLine()
if e != nil {
panic(e)
}
s.buf = append(s.buf, l...)
if !p {
break
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0