Submission #2939499


Source Code Expand

package main

import "fmt"

// 2018-08-03T23:14:25+0800
// 2018-08-03T23:24:36+0800
// 2018-08-03T23:54:09+0800 # @see https://arc063.contest.atcoder.jp/submissions/2939452
// 2018-08-04T00:02:23+0800 # @see https://arc063.contest.atcoder.jp/submissions/2939465
// 2018-08-04T00:23:32+0800
func main() {
	var N, T int
	fmt.Scanf("%d%d", &N, &T)
	A := make([]int, N)
	pa := make([]int, N)
	pb := make([]int, N)
	fmt.Scanf("%d", &A[0])
	pa[0] = A[0]
	for i := 1; i < N; i++ {
		fmt.Scanf("%d", &A[i])
		if A[i] < pa[i-1] {
			pa[i] = A[i]
		} else {
			pa[i] = pa[i-1]
		}
	}
	pb[N-1] = A[N-1]
	for i := N - 2; i >= 0; i-- {
		if A[i] > pb[i+1] {
			pb[i] = A[i]
		} else {
			pb[i] = pb[i+1]
		}
	}
	t := 0
	max := -1
	// (1, 5), (2, 6)
	out := make(map[int]map[int]bool)
	for i := 1; i < N; i++ {
		t = pb[i] - pa[i-1]
		if t >= max {
			max = t
			if out[t] == nil {
				out[t] = make(map[int]bool)
			}
			out[t][pb[i]] = true
		}
	}
	fmt.Println(len(out[max]))
}

func main1() {
	var N, T int
	fmt.Scanf("%d%d", &N, &T)
	A := make([]int, N)
	AA := make([]int, N)
	iAA := 0
	fmt.Scanf("%d", &A[0])
	AA[0] = A[0]
	iAA++
	inc := true
	for i := 1; i < N; i++ {
		fmt.Scanf("%d", &A[i])
		if i == 1 {
			inc = A[1] > A[0]
		}
		if (inc && A[i] < A[i-1]) || (!inc && A[i] > A[i-1]) {
			AA[iAA] = A[i-1]
			iAA ++
			inc = !inc
		}
	}
	AA[iAA] = A[N-1]
	iAA ++
	A = AA
	N = iAA
	pa := make([]int, N)
	pb := make([]int, N)
	pa[0] = A[0]
	for i := 1; i < N; i++ {
		if A[i] < pa[i-1] {
			pa[i] = A[i]
		} else {
			pa[i] = pa[i-1]
		}
	}
	pb[N-1] = A[N-1]
	for i := N - 2; i >= 0; i-- {
		if A[i] > pb[i+1] {
			pb[i] = A[i]
		} else {
			pb[i] = pb[i+1]
		}
	}
	out := 0
	t := 0
	max := -1
	end := -1
	for i := 1; i < N; i++ {
		t = pb[i] - pa[i-1]
		if t > max && end != pb[i] {
			max = t
			end = pb[i]
			out = 1
		} else if t == max {
			out++
		}
	}
	fmt.Println(out)
}

Submission Info

Submission Time
Task D - An Invisible Hand
User zhanbei
Language Go (1.6)
Score 400
Code Size 1980 Byte
Status AC
Exec Time 690 ms
Memory 5504 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 15
Set Name Test Cases
sample sample_01.txt, sample_02.txt, sample_03.txt
All large_01.txt, large_02.txt, random_01.txt, random_02.txt, sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, spec_01.txt, spec_02.txt, spec_03.txt, spec_04.txt, spec_05.txt, spec_06.txt
Case Name Status Exec Time Memory
large_01.txt AC 690 ms 5504 KB
large_02.txt AC 446 ms 5376 KB
random_01.txt AC 681 ms 5504 KB
random_02.txt AC 677 ms 5504 KB
sample_01.txt AC 1 ms 512 KB
sample_02.txt AC 1 ms 512 KB
sample_03.txt AC 1 ms 512 KB
small_01.txt AC 1 ms 512 KB
small_02.txt AC 1 ms 512 KB
spec_01.txt AC 685 ms 5504 KB
spec_02.txt AC 680 ms 5504 KB
spec_03.txt AC 683 ms 5504 KB
spec_04.txt AC 676 ms 5504 KB
spec_05.txt AC 679 ms 5376 KB
spec_06.txt AC 683 ms 5504 KB