結果
問題 | No.489 株に挑戦 |
ユーザー | mban |
提出日時 | 2017-07-25 09:49:59 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 230 ms / 1,000 ms |
コード長 | 3,449 bytes |
コンパイル時間 | 3,137 ms |
コンパイル使用メモリ | 107,704 KB |
実行使用メモリ | 28,380 KB |
最終ジャッジ日時 | 2023-09-27 05:48:49 |
合計ジャッジ時間 | 9,413 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 185 ms
24,232 KB |
testcase_01 | AC | 136 ms
23,064 KB |
testcase_02 | AC | 65 ms
22,112 KB |
testcase_03 | AC | 65 ms
21,896 KB |
testcase_04 | AC | 62 ms
21,800 KB |
testcase_05 | AC | 66 ms
23,940 KB |
testcase_06 | AC | 65 ms
22,056 KB |
testcase_07 | AC | 66 ms
21,848 KB |
testcase_08 | AC | 66 ms
23,812 KB |
testcase_09 | AC | 66 ms
23,896 KB |
testcase_10 | AC | 66 ms
21,776 KB |
testcase_11 | AC | 67 ms
23,892 KB |
testcase_12 | AC | 67 ms
21,856 KB |
testcase_13 | AC | 66 ms
21,972 KB |
testcase_14 | AC | 67 ms
23,892 KB |
testcase_15 | AC | 73 ms
21,908 KB |
testcase_16 | AC | 197 ms
28,308 KB |
testcase_17 | AC | 82 ms
21,888 KB |
testcase_18 | AC | 142 ms
22,832 KB |
testcase_19 | AC | 122 ms
24,836 KB |
testcase_20 | AC | 198 ms
26,320 KB |
testcase_21 | AC | 93 ms
22,556 KB |
testcase_22 | AC | 81 ms
23,916 KB |
testcase_23 | AC | 146 ms
27,148 KB |
testcase_24 | AC | 222 ms
26,340 KB |
testcase_25 | AC | 63 ms
21,564 KB |
testcase_26 | AC | 202 ms
26,208 KB |
testcase_27 | AC | 230 ms
26,400 KB |
testcase_28 | AC | 66 ms
21,872 KB |
testcase_29 | AC | 62 ms
23,636 KB |
testcase_30 | AC | 197 ms
26,368 KB |
testcase_31 | AC | 197 ms
24,444 KB |
testcase_32 | AC | 152 ms
24,936 KB |
testcase_33 | AC | 218 ms
28,380 KB |
testcase_34 | AC | 206 ms
26,516 KB |
testcase_35 | AC | 118 ms
24,792 KB |
testcase_36 | AC | 83 ms
21,952 KB |
testcase_37 | AC | 137 ms
25,028 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections; using System.Collections.Generic; using System.Collections.Specialized; using System.Text; using System.Text.RegularExpressions; using System.Linq; using System.IO; class Program { static void Main() { new Magatro().Solve(); } } struct S { public int Index, Num; public S(int index, int num) { Index = index; Num = num; } } class Magatro { private int N, D, K; private S[] X; private void Scan() { var line = Console.ReadLine().Split(' '); N = int.Parse(line[0]); D = int.Parse(line[1]); K = int.Parse(line[2]); X = new S[N]; for (int i = 0; i < N; i++) { X[i] = new S(i, int.Parse(Console.ReadLine())); } } private int Compare(S a, S b) { if (a.Num != b.Num) { return -a.Num.CompareTo(b.Num); } else { return -a.Index.CompareTo(b.Index); } } public void Solve() { Scan(); int max = 0; int l = -1, r = -1; bool flag = false; var segtree = new SegmentTree<S>(X, Compare, new S(-1, int.MaxValue)); for (int i = 1; i < N; i++) { int left = Math.Max(i - D, 0); S min = segtree.Query(left, i); if (X[i].Num - min.Num > max) { flag = true; l = min.Index; r = i; max = X[i].Num - min.Num; } } if (flag) { Console.WriteLine((long)K * max); Console.WriteLine($"{l} {r}"); } else { Console.WriteLine(0); } } } class SegmentTree<T> { private Comparison<T> Comparison; private int N; private T[] Tree; private T Min; public SegmentTree(int length, Comparison<T> comparition, T min) { for (N = 1; N <= length; N *= 2) ; Comparison = comparition; Tree = (new T[2 * N - 1]).Select(i => min).ToArray(); Min = min; } public SegmentTree(T[] array, Comparison<T> comparition, T min) : this(array.Length, comparition, min) { for (int i = 0; i < array.Length; i++) { Update(i, array[i]); } } /// <summary> /// index(0_indexed)をvに更新 /// </summary> /// <param name="index"></param> /// <param name="v"></param> public void Update(int index, T v) { int i = index + N - 1; Tree[i] = v; while (i > 0) { i = (i - 1) / 2; Tree[i] = Max(Tree[i * 2 + 1], Tree[i * 2 + 2]); } } /// <summary> /// [left,right)の最大値 /// </summary> /// <param name="left"></param> /// <param name="right"></param> /// <returns></returns> public T Query(int left, int right) { return Query(left, right, 0, 0, N); } private T Query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return Min; if (a <= l && r <= b) { return Tree[k]; } else { T vl = Query(a, b, k * 2 + 1, l, (l + r) / 2); T vr = Query(a, b, k * 2 + 2, (l + r) / 2, r); return Max(vl, vr); } } private T Max(T a, T b) { return Comparison(a, b) >= 0 ? a : b; } }