結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-07-30 18:10:28 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 89 ms / 1,000 ms |
コード長 | 3,833 bytes |
コンパイル時間 | 1,019 ms |
コンパイル使用メモリ | 119,236 KB |
実行使用メモリ | 33,024 KB |
最終ジャッジ日時 | 2024-07-19 23:55:41 |
合計ジャッジ時間 | 3,829 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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.Generic;using System.IO;using System.Linq;using System.Numerics;using System.Text;using static System.Console;using static System.Convert;using static System.Math;using static Extentions;class IO{int idx;string[] input;public IO(TextReader reader){input = reader.ReadToEnd().Split(new[] { " ", "\n", "\r" },StringSplitOptions.RemoveEmptyEntries);}T Get<T>(Func<string, T> parser) => parser(input[idx++]);public string S => Get(s => s);public char C => Get(char.Parse);public int I => Get(int.Parse);public long L => Get(long.Parse);public double F => Get(double.Parse);public decimal D => Get(decimal.Parse);public BigInteger B => Get(BigInteger.Parse);T[] Gets<T>(int n, Func<string, T> parser)=> input.Skip((idx += n) - n).Take(n).Select(parser).ToArray();public string[] Ss(int n) => Gets(n, s => s);public char[] Cs(int n) => Gets(n, char.Parse);public int[] Is(int n) => Gets(n, int.Parse);public long[] Ls(int n) => Gets(n, long.Parse);public double[] Fs(int n) => Gets(n, double.Parse);public decimal[] Ds(int n) => Gets(n, decimal.Parse);public BigInteger[] Bs(int n) => Gets(n, BigInteger.Parse);public void Write<T>(params T[] xs) => WriteLine(string.Join(" ", xs));public void Write(params object[] xs) => WriteLine(string.Join(" ", xs));}class SegmentTree<T>{int n;T[] tree;T id;Func<T, T, T> ope;public SegmentTree(int n, T id, Func<T, T, T> ope) : this(id, ope){this.n = 1;while (this.n < n) this.n *= 2;tree = Enumerable.Repeat(id, this.n * 2).ToArray();}public SegmentTree(T[] xs, T id, Func<T, T, T> ope) : this(id, ope){n = 1;while (n < xs.Length) n *= 2;tree = new T[n * 2];for (var i = 0; i < n; i++)tree[i + n] = i < xs.Length ? xs[i] : id;for (var i = n - 1; i > 0; i--)tree[i] = ope(tree[i * 2], tree[i * 2 + 1]);}SegmentTree(T id, Func<T, T, T> ope){this.id = id;this.ope = ope;}public T this[int i]{get { return tree[i + n]; }set{tree[i += n] = value;for (i >>= 1; i > 0; i >>= 1)tree[i] = ope(tree[i * 2], tree[i * 2 + 1]);}}public T this[int i, int j]{get{var r = id;i += n;j += n + 1;for (; i < j; i >>= 1, j >>= 1){if ((j & 1) != 0) r = ope(r, tree[--j]);if ((i & 1) != 0) r = ope(r, tree[i++]);}return r;}}}static class Extentions{}static class Program{public static void Main(){var sw = new StreamWriter(OpenStandardOutput()) { NewLine = "\n" };#if DEBUGsw.AutoFlush = true;#elsesw.AutoFlush = false;#endifSetOut(sw);Solve(new IO(In));Out.Flush();}static void Solve(IO io){var n = io.I;var d = io.I;var k = io.L;var x = io.Ls(n);var st = new SegmentTree<long>(x, 0, Max);var max = 0L;var maxi = 0;for (var i = 0; i < n; i++){var t = st[i, Min(n - 1, i + d)];if (t - x[i] > max){max = t - x[i];maxi = i;}}var p = maxi;var q = maxi + Array.FindIndex(x.Skip(maxi).ToArray(),a => a == max + x[maxi]);max *= k;if (max <= 0) io.Write(0);else{io.Write(max);io.Write(p, q);}}}