結果

問題 No.1826 Fruits Collecting
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-03 16:44:20
言語 Go
(1.22.1)
結果
AC  
実行時間 364 ms / 2,000 ms
コード長 2,493 bytes
コンパイル時間 11,490 ms
コンパイル使用メモリ 238,336 KB
実行使用メモリ 21,940 KB
最終ジャッジ日時 2024-09-17 22:04:49
合計ジャッジ時間 18,837 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,816 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 5 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 152 ms
9,848 KB
testcase_06 AC 244 ms
16,448 KB
testcase_07 AC 174 ms
10,100 KB
testcase_08 AC 20 ms
6,944 KB
testcase_09 AC 251 ms
16,084 KB
testcase_10 AC 169 ms
9,844 KB
testcase_11 AC 153 ms
9,596 KB
testcase_12 AC 62 ms
6,944 KB
testcase_13 AC 30 ms
6,940 KB
testcase_14 AC 49 ms
6,944 KB
testcase_15 AC 360 ms
19,304 KB
testcase_16 AC 358 ms
19,304 KB
testcase_17 AC 348 ms
18,800 KB
testcase_18 AC 359 ms
19,300 KB
testcase_19 AC 361 ms
19,300 KB
testcase_20 AC 350 ms
21,452 KB
testcase_21 AC 351 ms
18,792 KB
testcase_22 AC 364 ms
19,304 KB
testcase_23 AC 355 ms
18,792 KB
testcase_24 AC 349 ms
19,304 KB
testcase_25 AC 1 ms
6,940 KB
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 1 ms
6,944 KB
testcase_28 AC 1 ms
6,940 KB
testcase_29 AC 1 ms
6,940 KB
testcase_30 AC 72 ms
7,820 KB
testcase_31 AC 144 ms
9,464 KB
testcase_32 AC 88 ms
8,204 KB
testcase_33 AC 288 ms
21,940 KB
testcase_34 AC 244 ms
19,132 KB
testcase_35 AC 61 ms
6,940 KB
testcase_36 AC 290 ms
21,568 KB
testcase_37 AC 208 ms
18,924 KB
testcase_38 AC 140 ms
12,636 KB
testcase_39 AC 210 ms
15,360 KB
testcase_40 AC 265 ms
18,264 KB
testcase_41 AC 57 ms
6,940 KB
testcase_42 AC 10 ms
6,940 KB
testcase_43 AC 2 ms
6,940 KB
testcase_44 AC 1 ms
6,944 KB
testcase_45 AC 1 ms
6,940 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