結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-07-25 09:49:59 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 197 ms / 1,000 ms |
コード長 | 3,449 bytes |
コンパイル時間 | 2,643 ms |
コンパイル使用メモリ | 115,116 KB |
実行使用メモリ | 33,208 KB |
最終ジャッジ日時 | 2024-07-19 23:55:24 |
合計ジャッジ時間 | 8,839 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
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;}}