結果

問題 No.1826 Fruits Collecting
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-03 16:44:20
言語 Go
(1.22.1)
結果
AC  
実行時間 431 ms / 2,000 ms
コード長 2,493 bytes
コンパイル時間 12,902 ms
コンパイル使用メモリ 221,152 KB
実行使用メモリ 25,896 KB
最終ジャッジ日時 2023-10-18 01:05:01
合計ジャッジ時間 21,928 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 3 ms
4,348 KB
testcase_02 AC 4 ms
4,348 KB
testcase_03 AC 5 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 167 ms
9,688 KB
testcase_06 AC 277 ms
15,884 KB
testcase_07 AC 199 ms
10,700 KB
testcase_08 AC 22 ms
5,616 KB
testcase_09 AC 273 ms
15,360 KB
testcase_10 AC 185 ms
10,156 KB
testcase_11 AC 179 ms
9,388 KB
testcase_12 AC 72 ms
6,068 KB
testcase_13 AC 36 ms
5,636 KB
testcase_14 AC 58 ms
6,452 KB
testcase_15 AC 428 ms
24,628 KB
testcase_16 AC 426 ms
25,304 KB
testcase_17 AC 428 ms
23,816 KB
testcase_18 AC 426 ms
24,656 KB
testcase_19 AC 424 ms
24,612 KB
testcase_20 AC 431 ms
25,896 KB
testcase_21 AC 431 ms
25,328 KB
testcase_22 AC 429 ms
24,592 KB
testcase_23 AC 426 ms
25,336 KB
testcase_24 AC 427 ms
24,592 KB
testcase_25 AC 1 ms
4,348 KB
testcase_26 AC 1 ms
4,348 KB
testcase_27 AC 2 ms
4,348 KB
testcase_28 AC 1 ms
4,348 KB
testcase_29 AC 1 ms
4,348 KB
testcase_30 AC 86 ms
7,960 KB
testcase_31 AC 170 ms
9,956 KB
testcase_32 AC 103 ms
8,032 KB
testcase_33 AC 352 ms
20,700 KB
testcase_34 AC 295 ms
19,028 KB
testcase_35 AC 68 ms
6,504 KB
testcase_36 AC 347 ms
20,620 KB
testcase_37 AC 253 ms
19,096 KB
testcase_38 AC 170 ms
12,372 KB
testcase_39 AC 248 ms
15,364 KB
testcase_40 AC 313 ms
18,584 KB
testcase_41 AC 68 ms
6,188 KB
testcase_42 AC 11 ms
4,348 KB
testcase_43 AC 1 ms
4,348 KB
testcase_44 AC 1 ms
4,348 KB
testcase_45 AC 1 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	fmt.Fscan(in, &n)
	goods := make([][3]int, n) // time, pos, score
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &goods[i][0], &goods[i][1], &goods[i][2])
	}

	txs := make([][3]int, 0, n)
	set := map[int]struct{}{0: {}} // start pos
	for i := 0; i < n; i++ {
		t, x, s := goods[i][0], goods[i][1], goods[i][2]
		if abs(x) <= t { // reachable
			txs = append(txs, [3]int{t + x, t - x, s})
			set[t-x] = struct{}{}
		}
	}

	sort.Slice(txs, func(i, j int) bool {
		if txs[i][0] == txs[j][0] {
			return txs[i][1] < txs[j][1]
		}
		return txs[i][0] < txs[j][0]
	})
	sorted := make([]int, 0, len(set))
	for k := range set {
		sorted = append(sorted, k)
	}
	sort.Ints(sorted)
	mp := make(map[int]int, len(sorted))
	for i, v := range sorted {
		mp[v] = i
	}

	seg := NewFenwickTreePrefix(len(sorted))
	seg.Set(0, 0)
	for i := 0; i < len(txs); i++ {
		x, s := txs[i][1], txs[i][2]
		pos := mp[x]
		curMax := seg.Query(pos+1) + s
		seg.Set(pos, curMax)
	}
	fmt.Fprintln(out, seg.Query(len(sorted)))

}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

type S = int

const INF int = 1e18

func (*FenwickTreePrefix) e() S        { return -INF }
func (*FenwickTreePrefix) op(a, b S) S { return max(a, b) }
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

type FenwickTreePrefix struct {
	n    int
	data []S
}

func NewFenwickTreePrefix(n int) *FenwickTreePrefix {
	res := &FenwickTreePrefix{n, make([]S, n+1)}
	for i := 0; i < n+1; i++ {
		res.data[i] = res.e()
	}
	return res
}

func NewFenwickTreePrefixWithSlice(nums []S) *FenwickTreePrefix {
	n := len(nums)
	res := &FenwickTreePrefix{n, make([]S, n+1)}
	for i := n; i > 0; i-- {
		res.data[i] = res.op(res.data[i], nums[i-1])
		if p := i + (i & -i); p <= n {
			res.data[p] = res.op(res.data[p], res.data[i])
		}
	}
	return res
}

// 单点更新index处的元素.
// 0 <= index < n
func (f *FenwickTreePrefix) Set(index int, value S) {
	for index++; index <= f.n; index += index & -index {
		f.data[index] = f.op(f.data[index], value)
	}
}

// 查询前缀区间 [0,right) 的值.
// 0 <= right <= n
func (f *FenwickTreePrefix) Query(right int) S {
	res := f.e()
	if right > f.n {
		right = f.n
	}
	for ; right > 0; right -= right & -right {
		res = f.op(res, f.data[right])
	}
	return res
}
0