結果
問題 | No.448 ゆきこーだーの雨と雪 (3) |
ユーザー | 紙ぺーぱー |
提出日時 | 2016-11-18 23:22:08 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 218 ms / 2,000 ms |
コード長 | 7,602 bytes |
コンパイル時間 | 2,499 ms |
コンパイル使用メモリ | 111,544 KB |
実行使用メモリ | 32,276 KB |
最終ジャッジ日時 | 2023-09-02 12:50:41 |
合計ジャッジ時間 | 9,026 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 51 ms
22,472 KB |
testcase_01 | AC | 51 ms
20,424 KB |
testcase_02 | AC | 49 ms
22,476 KB |
testcase_03 | AC | 50 ms
22,488 KB |
testcase_04 | AC | 48 ms
20,340 KB |
testcase_05 | AC | 49 ms
20,372 KB |
testcase_06 | AC | 51 ms
22,476 KB |
testcase_07 | AC | 50 ms
20,372 KB |
testcase_08 | AC | 50 ms
20,436 KB |
testcase_09 | AC | 50 ms
22,468 KB |
testcase_10 | AC | 51 ms
22,340 KB |
testcase_11 | AC | 50 ms
20,312 KB |
testcase_12 | AC | 51 ms
20,424 KB |
testcase_13 | AC | 73 ms
21,092 KB |
testcase_14 | AC | 76 ms
23,392 KB |
testcase_15 | AC | 118 ms
24,332 KB |
testcase_16 | AC | 153 ms
30,120 KB |
testcase_17 | AC | 173 ms
30,432 KB |
testcase_18 | AC | 68 ms
23,108 KB |
testcase_19 | AC | 206 ms
31,588 KB |
testcase_20 | AC | 104 ms
22,864 KB |
testcase_21 | AC | 211 ms
29,628 KB |
testcase_22 | AC | 106 ms
26,024 KB |
testcase_23 | AC | 200 ms
29,664 KB |
testcase_24 | AC | 87 ms
24,224 KB |
testcase_25 | AC | 211 ms
31,592 KB |
testcase_26 | AC | 67 ms
21,120 KB |
testcase_27 | AC | 163 ms
30,128 KB |
testcase_28 | AC | 153 ms
27,880 KB |
testcase_29 | AC | 103 ms
23,992 KB |
testcase_30 | AC | 206 ms
29,772 KB |
testcase_31 | AC | 70 ms
19,296 KB |
testcase_32 | AC | 71 ms
21,308 KB |
testcase_33 | AC | 216 ms
32,276 KB |
testcase_34 | AC | 215 ms
30,136 KB |
testcase_35 | AC | 213 ms
30,200 KB |
testcase_36 | AC | 203 ms
30,192 KB |
testcase_37 | AC | 218 ms
30,168 KB |
testcase_38 | AC | 215 ms
30,176 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.Linq; using System.Linq.Expressions; using System.Collections.Generic; using Debug = System.Diagnostics.Debug; using StringBuilder = System.Text.StringBuilder; using System.Numerics; using Point = System.Numerics.Complex; using Number = System.Int64; namespace Program { public class Solver { public void Solve() { var n = sc.Integer(); var k = sc.Long(); var T = new long[n]; var D = new long[n]; for (int i = 0; i < n; i++) { T[i] = sc.Long(); D[i] = sc.Long(); } var l = -1; var r = 1000000000 + 50; for (int _ = 0; _ < 35; _++) { var m = (l + r) / 2; var ok = true; var last = -10000000000L; for (int i = 0; i < n; i++) { if (D[i] <= m) continue; else { if (last + k > T[i]) { ok = false; break; } last = T[i]; } } if (ok) r = m; else l = m; } var dp = new long[n + 1]; for (int i = 1; i <= n; i++) dp[i] = 1L << 60; var seg = new RMQSegmentTree(n); for (int i = 0; i < n; i++) seg.Update(i, D[i]); var cum = new long[n + 1]; for (int i = 0; i < n; i++) cum[i + 1] = cum[i] + D[i]; for (int i = 0; i < n; i++) { var p = Array.BinarySearch(T, T[i] + k); if (p < 0) p = ~p; if (D[i] <= r) { dp[i + 1] = Math.Min(dp[i + 1], dp[i] + D[i]); if (seg.Query(i, p) <= r) { dp[p] = Math.Min(dp[p], dp[i] + cum[p] - cum[i + 1]); } } else { dp[p] = Math.Min(dp[p], dp[i] + cum[p] - cum[i + 1]); } } IO.Printer.Out.WriteLine(r); IO.Printer.Out.WriteLine(dp[n]); } public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput()); static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; } static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; } } } #region main static class Ex { static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); } static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); } static public void Main() { var solver = new Program.Solver(); solver.Solve(); Program.IO.Printer.Out.Flush(); } } #endregion #region Ex namespace Program.IO { using System.IO; using System.Text; using System.Globalization; public class Printer: StreamWriter { static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; } public static Printer Out { get; set; } public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { } public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { } public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); } public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); } } public class StreamScanner { public StreamScanner(Stream stream) { str = stream; } public readonly Stream str; private readonly byte[] buf = new byte[1024]; private int len, ptr; public bool isEof = false; public bool IsEndOfStream { get { return isEof; } } private byte read() { if (isEof) return 0; if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } } return buf[ptr++]; } public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; } public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } public string ScanLine() { var sb = new StringBuilder(); for (var b = Char(); b != '\n'; b = (char)read()) if (b == 0) break; else if (b != '\r') sb.Append(b); return sb.ToString(); } public long Long() { if (isEof) return long.MinValue; long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != 0 && b != '-' && (b < '0' || '9' < b)); if (b == 0) return long.MinValue; if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = ret * 10 + b - '0'; } } public int Integer() { return (isEof) ? int.MinValue : (int)Long(); } public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; } private T[] enumerate<T>(int n, Func<T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(); return a; } public char[] Char(int n) { return enumerate(n, Char); } public string[] Scan(int n) { return enumerate(n, Scan); } public double[] Double(int n) { return enumerate(n, Double); } public int[] Integer(int n) { return enumerate(n, Integer); } public long[] Long(int n) { return enumerate(n, Long); } } } #endregion #region RMQ Segment Tree public class RMQSegmentTree { const Number ZERO = Number.MinValue; int n; Number[] data; public RMQSegmentTree(int size) { n = 1; while (n < size) n <<= 1; data = new Number[n << 1]; for (int i = 0; i < data.Length; i++) data[i] = ZERO; } public void Update(int k, Number v) { k += n; data[k] = v; k >>= 1; while (k > 0) { data[k] = merge(data[k << 1], data[(k << 1) + 1]); k >>= 1; } } public Number Query(int a, int b) { return query(a, b, 1, 0, n); } private Number query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return ZERO; if (a <= l && r <= b) return data[k]; else { var vl = query(a, b, k << 1, l, (l + r) >> 1); var vr = query(a, b, (k << 1) + 1, (l + r) >> 1, r); return merge(vl, vr); } } Number merge(Number l, Number r) { return Math.Max(l, r); } public Number[] Items { get { var ret = new Number[n]; for (int i = 0; i < n; i++) ret[i] = data[i + n]; return ret; } } } #endregion