結果

問題 No.448 ゆきこーだーの雨と雪 (3)
ユーザー 14番14番
提出日時 2016-12-16 00:57:11
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 8,687 bytes
コンパイル時間 2,315 ms
コンパイル使用メモリ 104,912 KB
実行使用メモリ 56,532 KB
最終ジャッジ日時 2023-08-20 08:28:30
合計ジャッジ時間 10,167 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
28,248 KB
testcase_01 AC 71 ms
22,100 KB
testcase_02 AC 73 ms
23,904 KB
testcase_03 AC 71 ms
23,824 KB
testcase_04 AC 73 ms
21,896 KB
testcase_05 AC 74 ms
24,020 KB
testcase_06 AC 74 ms
22,168 KB
testcase_07 AC 73 ms
23,900 KB
testcase_08 AC 73 ms
21,848 KB
testcase_09 AC 72 ms
21,888 KB
testcase_10 AC 72 ms
22,000 KB
testcase_11 AC 72 ms
23,988 KB
testcase_12 AC 73 ms
21,964 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 TLE -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{
    public void Proc() {
        Reader.IsDebug = false;
        long[] inpt = Reader.ReadLine().Split(' ').Select(a=>long.Parse(a)).ToArray();

        int inputCount = (int)inpt[0];
        this.Neru = inpt[1];

        for(int i=0; i<inputCount; i++) {
            SagyoList.Add(new Sagyo(Reader.ReadLine().Split(' ').Select(a=>long.Parse(a)).ToArray()));
        }
        OrderedSagyoList = SagyoList.OrderBy(a=>a.Dif).ToList();
        long max = this.MaxNani(0, OrderedSagyoList.Last().Dif, OrderedSagyoList);
        long total = this.GetTotal(max, 0);
        Console.WriteLine(max);
        Console.WriteLine(total);
    }

    private Dictionary<int, long> dic = new Dictionary<int, long>();
    private long GetTotal(long max, int idx) {
        if(dic.ContainsKey(idx)) {
            return dic[idx];
        }
        if(idx >= this.SagyoList.Count) {
            return 0;
        }

        long ans = 0;
        long nextTime;
        int nextIdx = -1;
        if(this.SagyoList[idx].Dif > max) {
            nextTime = this.SagyoList[idx].Time + this.Neru;
            for(int i=idx+1; i<this.SagyoList.Count; i++) {
                if(this.SagyoList[i].Time >= nextTime) {
                    nextIdx = i;
                    break;
                } else {
                    ans+=this.SagyoList[i].Dif;
                }
            }
            if(nextIdx >= 0) {
                ans+=this.GetTotal(max, nextIdx);
            }
        } else {
            ans = this.GetTotal(max, idx+1) + this.SagyoList[idx].Dif;
            nextTime = this.SagyoList[idx].Time + this.Neru;
            long tmp = 0;
            for(int i=idx+1; i<this.SagyoList.Count; i++) {
                if(this.SagyoList[i].Time >= nextTime) {
                    nextIdx = i;
                    break;
                } else if(this.SagyoList[i].Dif > max) {
                    tmp+=this.SagyoList[idx].Dif;
                    nextIdx = -1;
                    ans = Math.Min(this.GetTotal(max, i) + tmp, ans);
                    break;
                } else {
                    tmp+=this.SagyoList[i].Dif;
                }
            }
            if(nextIdx >= 0) {
                ans =  Math.Min(ans, this.GetTotal(max, nextIdx) + tmp);
            } else if(idx == this.SagyoList.Count - 1) {
                ans = 0;
            }
        }
        this.dic[idx] = ans;
        return ans;
    }

    private long MaxNani(long min, long max, List<Sagyo> list) {
        if(max-min <= 1) {
            if(Kakunin(min, list)) {
                return min;
            } else {
                return max;
            }
        }
        long mid = (min+max)/2;

        if(Kakunin(mid, list)) {
            return MaxNani(min, mid, list);
        } else {
            return MaxNani(mid, max, list);
        }
    }
    private bool Kakunin(long target, List<Sagyo> list) {
        int idx = this.GetIndex(target, list, 0, list.Count - 1);
        List<Sagyo> sub = list.Skip(idx).OrderBy(a=>a.Time).ToList();
        for(int i=1; i<sub.Count; i++) {
            if(sub[i].Time - sub[i-1].Time < this.Neru) {
                return false;
            }
        }
        return true;
    }

    private int GetIndex(long targetNanido, List<Sagyo> orderedList, int min, int max) {
        if(max-min<=1) {
            if(orderedList[min].Dif > targetNanido) {
                return min;
            } else {
                return max;
            }
        }
        int mid = (min+max)/2;
        if(orderedList[mid].Dif > targetNanido) {
            return this.GetIndex(targetNanido, orderedList, min, mid);
        } else {
            return this.GetIndex(targetNanido, orderedList, mid, max);
        }
    }

    List<Sagyo> OrderedSagyoList = new List<Sagyo>();
    List<Sagyo> SagyoList = new List<Sagyo>();

    public struct Sagyo {
        public long Time;
        public long Dif;
        public Sagyo(long[] init) {
            this.Time = init[0];
            this.Dif = init[1];
        }
    }

    private long Neru = 0;


    public class Reader {
        public static bool IsDebug = true;
        private static System.IO.StringReader SReader;
        private static string InitText = @"


345 140
32 4348
48 25211
75 60352
186 6070
219 1804
354 91496
435 9843
436 32324
541 26856
579 27340
661 2514
669 21453
801 25297
862 21733
1002 65226
1036 31353
1044 5458
1169 25734
1232 47401
1249 34429
1251 40126
1305 12150
1311 9419
1352 28220
1387 67411
1434 26760
1462 54311
1468 6193
1479 22968
1487 38979
1489 32430
1499 9866
1766 21179
1793 24139
1806 11610
1858 36179
1917 24503
1925 45950
1961 12531
1981 3244
2011 57524
2134 6235
2135 984
2307 36721
2358 46836
2423 9192
2451 5520
2536 7437
2574 2246
2641 59681
2649 32204
2843 4696
2916 29639
3010 27257
3065 22605
3078 23532
3186 3863
3305 37356
3314 1478
3394 11886
3436 20395
3451 22222
3494 11868
3528 13338
3610 14815
3751 27478
3995 17810
4186 3724
4291 42545
4606 16344
4610 8812
4719 15661
4844 43388
4893 7530
5127 25218
5328 1268
5479 19402
5621 6723
5804 68081
6023 1984
6058 11453
6073 6717
6171 61214
6263 7455
6569 6820
6719 33259
6741 55329
6786 36029
6830 37372
7006 24220
7088 34617
7323 13311
7569 2190
7579 20312
7631 2767
7663 25799
7731 2622
7840 51445
8023 25879
8100 37084
8550 32520
8611 27197
8634 690
8689 520
8732 38501
8987 14510
9107 6084
9310 31567
9333 50409
9376 3372
9437 3478
9521 48336
9532 39397
9881 8342
10163 81866
10217 34253
10288 8965
10327 6423
10412 10298
10461 38815
10795 21114
11077 24911
11212 80812
11351 51532
11583 2793
11587 27526
11619 5817
11633 60792
11693 56952
11917 483
11938 1310
11981 19180
12036 2454
12231 37679
12239 13756
12270 30333
12457 13272
12612 48692
12834 2035
12993 54632
13130 42320
13191 46098
13336 899
14044 11814
14214 27001
14258 13622
14464 12975
14478 22520
14629 1967
14754 28524
14830 49659
15205 32113
15285 35907
15406 33052
15462 3475
15495 45042
15638 33104
15749 27423
15975 21259
16000 18416
16682 57682
17228 35470
17230 18314
17275 3805
17332 35114
17385 34343
17600 13128
17872 4016
18301 7226
18384 20946
18597 13995
18604 12621
18912 59041
18931 17177
19154 75446
19841 64201
19864 35877
20309 86597
20565 21804
20761 57763
21025 3576
21036 23836
21174 66131
21431 35852
21479 16134
21504 691
21615 3350
22082 18318
22166 5974
22170 37940
22303 19568
22421 32214
22628 39319
22662 3679
22808 1586
22905 31798
22955 35710
22963 35151
23015 51303
23245 51530
23250 1717
23386 34236
23606 29987
23871 46709
24009 3473
24348 7135
24849 24245
25173 25571
25268 37840
25269 1194
25316 4133
25349 15310
25627 7621
25774 12431
25860 43333
25921 54338
26385 1585
26464 2885
26608 288
26805 161
27069 32251
27102 37614
27314 28680
27401 34780
27811 14461
27852 30440
27895 18193
27996 832
28818 28993
29459 21988
29793 56279
29815 2749
29899 49236
30137 38403
30325 3446
30631 20495
31110 1270
31316 17157
31350 33377
31768 2654
32234 29825
32304 38632
32373 32000
32428 5776
33072 9067
33354 30868
33780 786
34048 36459
34508 538
34598 19406
34867 9050
34889 18047
34942 25705
36184 2493
36311 60510
36475 7089
36539 41263
36549 76554
36684 5547
37497 9594
37637 16226
37865 78051
37952 64860
38746 9366
39131 33603
39516 6366
40026 6113
40053 53225
40648 8803
41485 28602
41506 27132
42938 9974
43264 18319
43523 6598
43695 10647
43961 53991
44159 6697
44431 80820
44801 4667
45487 7580
46324 74554
46498 34901
47584 47780
47721 22928
47961 19838
49470 46315
49613 378
49668 70627
50699 43967
51369 27386
51687 46783
51700 263
52091 31143
52264 807
52371 2663
52613 33694
52856 3419
52890 30321
52905 81789
53457 54568
54464 34352
55656 62362
55783 12025
56321 16197
58422 2406
58470 57291
59207 5258
59842 68070
59886 54947
59894 7916
60304 61020
60320 68386
60616 3901
60660 32334
60897 15079
62814 6211
63046 47579
63294 18452
65003 925
65346 25590
65791 72218
66571 18567
67408 14748
68350 23636
69238 40860
69334 17446
69453 15642
70649 48933
71953 86803
72901 14836
73669 3500
74150 7686
75246 8679
76201 34544
76481 2860
76841 54055
76996 1601
77702 26938
77721 14325
78516 53765
79235 6380
80039 2532
81016 36930
87331 81897
87421 58439



";
        public static string ReadLine() {
            if(IsDebug) {
                if(SReader == null) {
                    SReader = new System.IO.StringReader(InitText.Trim());
                }
                return SReader.ReadLine();
            } else {
                return Console.ReadLine();
            }
        }
    }
    public static void Main(string[] args)
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0