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 |
|
|
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 |