242742026-02-07 17:13:04ercseferencSzitakötő (50 pont)golangAccepted 50/50112ms17752 KiB
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	const maxCapacity = 1024 * 1024
	sc.Buffer(make([]byte, maxCapacity), maxCapacity)

	readInt := func() int {
		sc.Scan()
		i, _ := strconv.Atoi(sc.Text())
		return i
	}

	readInt64 := func() int64 {
		sc.Scan()
		i, _ := strconv.ParseInt(sc.Text(), 10, 64)
		return i
	}

	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	n := readInt()
	m := readInt()
	m--

	const mod int64 = 1e9 + 7

	if n == 3 {
		x, y, z := readInt64(), readInt64(), readInt64()
		if m == 0 {
			fmt.Fprint(writer, 0)
		} else if m == 1 {
			if x+y > z {
				fmt.Fprint(writer, 4)
			} else {
				fmt.Fprint(writer, 0)
			}
		} else if m == 2 {
			if x+y <= z {
				fmt.Fprint(writer, 8)
			} else {
				fmt.Fprint(writer, 4)
			}
		}
		return
	}

	s := make([]int64, n)
	s[0] = readInt64()
	for i := 1; i < n; i++ {
		s[i] = s[i-1] + readInt64()
	}

	getS := func(idx int) int64 {
		if idx < 0 {
			return 0
		}
		return s[idx]
	}

	t := s[m] - getS(m-1)
	poz := m - 1
	for poz >= 0 && t < s[poz] {
		t += s[poz] - getS(poz-1)
		poz--
	}

	var ans int64 = 1
	poz++
	for i := 0; i < poz; i++ {
		ans = (ans * 2) % mod
	}

	dp := make([]int64, n)
	dp[m-1] = 0
	dp[m] = ans
	leh := true

	for i := m + 1; i < n; i++ {
		x, y := m+1, i
		if 2*s[i-1] <= s[i] {
			leh = false
		}
		for leh && x != y {
			k := (x + y) / 2
			if 2*s[k-1] > s[i] {
				y = k
			} else {
				x = k + 1
			}
		}

		var prevDpVal int64 = 0
		if x-2 >= 0 {
			prevDpVal = dp[x-2]
		}
		dp[i] = (2*dp[i-1] - prevDpVal) % mod
		if dp[i] < 0 {
			dp[i] += mod
		}
	}

	if leh {
		res := (dp[n-1] - dp[n-2])
		res = (res * 2) % mod
		if res < 0 {
			res += mod
		}
		fmt.Fprint(writer, res)
	} else {
		fmt.Fprint(writer, 0)
	}
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/035ms13276 KiB
2Accepted0/0112ms17752 KiB
3Accepted1/135ms13456 KiB
4Accepted1/134ms12780 KiB
5Accepted1/125ms7936 KiB
6Accepted1/125ms8540 KiB
7Accepted1/125ms8444 KiB
8Accepted1/125ms8232 KiB
9Accepted1/124ms8556 KiB
10Accepted2/225ms8532 KiB
11Accepted2/224ms8472 KiB
12Accepted2/227ms8152 KiB
13Accepted2/227ms7860 KiB
14Accepted2/226ms7724 KiB
15Accepted2/226ms8348 KiB
16Accepted2/227ms8268 KiB
17Accepted2/226ms8048 KiB
18Accepted2/225ms8436 KiB
19Accepted2/227ms8328 KiB
20Accepted2/224ms8264 KiB
21Accepted1/124ms8308 KiB
22Accepted2/271ms10520 KiB
23Accepted2/271ms10188 KiB
24Accepted2/2100ms13584 KiB
25Accepted2/286ms13348 KiB
26Accepted2/275ms12340 KiB
27Accepted2/256ms9432 KiB
28Accepted2/271ms10704 KiB
29Accepted2/257ms9900 KiB
30Accepted2/283ms12932 KiB
31Accepted2/267ms10176 KiB