|

General

# Author Problem Lang Verdict Time Memory Sent Judged
226466440 Practice:
hulm
580B - 20 Go Time limit exceeded on test 15 2000 ms 10892 KB 2023-10-03 18:37:59 2023-10-03 18:37:59
→ Source
package main

import (
"fmt"
)

const N = 200005

var a, b [N]pair

type pair struct{ m, s int }

func Max(i, j int) int {
if i >= j {
return i
} else {
return j
}
}

func mergeSort(l, r int) {
if l >= r {
return
}
mid := (l + r) / 2
mergeSort(l, mid)
mergeSort(mid+1, r)
i, j := l, mid+1

pos := l
for i <= mid || j <= r {
if i == mid+1 {
b[pos] = a[j]
j++
} else if j == r+1 {
b[pos] = a[i]
i++
} else if a[i].m < a[j].m {
b[pos] = a[i]
i++
} else {
b[pos] = a[j]
j++
}
pos++
}
for i := l; i <= r; i++ {
a[i] = b[i]
}
}

func main() {
var n, d int
fmt.Scanf("%v %v\n", &n, &d)

for i := 0; i < n; i++ {
var f, s int
fmt.Scanf("%v %v\n", &f, &s)
a[i] = pair{f, s}
}
mergeSort(0, n-1)
ans, sum, l, r := 0, 0, 0, -1
for r < n {
r++
sum += a[r].s
// fmt.Printf("%v ->\n", r)
for a[r].m-a[l].m >= d {
// fmt.Printf("%v ", l)
sum -= a[l].s
l++
}
// fmt.Printf("\n")
ans = Max(ans, sum)
}

fmt.Printf("%v", ans)
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?