第2回 ドワンゴからの挑戦状 予選

Submission #1258560

Source codeソースコード

using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        string[] str = Console.ReadLine().Split(' ');
        int N = int.Parse(str[0]);
        AbsoluteSum Ab = new AbsoluteSum(N);
        int t = 0;
        for(int i=0;i<N;i++){
            str = Console.ReadLine().Split(' ');
            if(int.Parse(str[0]) != t){
                Ab.Min();
                t = int.Parse(str[0]);
            }
            Ab.Add(int.Parse(str[1]));
        }
        sb.Append(Ab.GetMin()+"\n");
    }
}
class AbsoluteSum{
    long minValue;
    Heap Lheap;
    Heap Rheap;
    public AbsoluteSum(int maxsize){
        minValue = 0;
        Lheap = new Heap(maxsize*2,false);
        Rheap = new Heap(maxsize*2,true);
    }
    public void Add(long X){
        if(Lheap.size != 0 && Lheap.Get() >= X){
            minValue += Lheap.Get() - X;
            Rheap.push(Lheap.pop());
            Lheap.push(X);
            Lheap.push(X);
        }
        else if(Rheap.size != 0 && Rheap.Get() <= X){
            minValue += X - Rheap.Get();
            Lheap.push(Rheap.pop());
            Rheap.push(X);
            Rheap.push(X);
        }
        else{
            Lheap.push(X);
            Rheap.push(X);
        }
    }
    public void Min(){
        Rheap.Clear();
    }
    public long GetMin(){
        return minValue;
    }
}
class Heap{
    public int size;
    long[] obj;
    bool B;
    public Heap(int maxsize,bool b0){
        size = 0;
        B = b0;
        obj = new long[maxsize];
    }
    //小さい順ならa<=b
    public bool Compare(long a,long b){
        return (B && a<=b) || (!B && a>=b);
    }
    public void push(long a){
        int i = size;
        size++;
        while(i > 0){
            int p = (i - 1)/2;
            if(Compare(obj[p],a)){
                obj[i] = a;
                break;
            }
            obj[i] = obj[p];
            i = p;
        }
        if(i == 0){
            obj[0] = a;
        }
    }
    public long pop(){
        long t = obj[0];
        int i = 0;
        size--;
        while(2*i+1 < size){
            int p = 2*i+1;
            if(p+1 < size && Compare(obj[p+1],obj[p])){
                p++;
            }
            if(Compare(obj[p],obj[size])){
                obj[i] = obj[p];
                i = p;
            }
            else{
                obj[i] = obj[size];
                break;
            }
        }
        if(2*i+1 >= size){
            obj[i] = obj[size];
        }
        return t;
    }
    public long Get(){
        return obj[0];
    }
    public void Clear(){
        for(int i=0;i<size;i++){
            obj[i] = 0; 
        }
        size = 0;
    }
}

Submission

Task問題 E - 花火
User nameユーザ名 lei
Created time投稿日時
Language言語 C# (Mono 4.6.2.0)
Status状態 AC
Score得点 160
Source lengthソースコード長 3070 Byte
File nameファイル名
Exec time実行時間 154 ms
Memory usageメモリ使用量 16588 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
Subtask1 30 / 30 sample_01.txt,sample_02.txt,sample_03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt,subtask1_23.txt,subtask1_24.txt,subtask1_25.txt,subtask1_26.txt,subtask1_27.txt,subtask1_28.txt,subtask1_29.txt,subtask1_30.txt,subtask1_31.txt,subtask1_32.txt,subtask1_33.txt,subtask1_34.txt,subtask1_35.txt,subtask1_36.txt,subtask1_37.txt,subtask1_38.txt,subtask1_39.txt,subtask1_40.txt,subtask1_41.txt,subtask1_42.txt
Subtask2 130 / 130 sample_01.txt,sample_02.txt,sample_03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt,subtask1_23.txt,subtask1_24.txt,subtask1_25.txt,subtask1_26.txt,subtask1_27.txt,subtask1_28.txt,subtask1_29.txt,subtask1_30.txt,subtask1_31.txt,subtask1_32.txt,subtask1_33.txt,subtask1_34.txt,subtask1_35.txt,subtask1_36.txt,subtask1_37.txt,subtask1_38.txt,subtask1_39.txt,subtask1_40.txt,subtask1_41.txt,subtask1_42.txt,subtask2_01.txt,subtask2_02.txt,subtask2_03.txt,subtask2_04.txt,subtask2_05.txt,subtask2_06.txt,subtask2_07.txt,subtask2_08.txt,subtask2_09.txt,subtask2_10.txt,subtask2_11.txt,subtask2_12.txt,subtask2_13.txt,subtask2_14.txt,subtask2_15.txt,subtask2_16.txt,subtask2_17.txt,subtask2_18.txt,subtask2_19.txt,subtask2_20.txt,subtask2_21.txt,subtask2_22.txt,subtask2_23.txt,subtask2_24.txt,subtask2_25.txt,subtask2_26.txt,subtask2_27.txt,subtask2_28.txt,subtask2_29.txt,subtask2_30.txt,subtask2_31.txt,subtask2_32.txt,subtask2_33.txt,subtask2_34.txt,subtask2_35.txt,subtask2_36.txt,subtask2_37.txt,subtask2_38.txt,subtask2_39.txt,subtask2_40.txt,subtask2_41.txt,subtask2_42.txt,subtask2_43.txt,subtask2_44.txt,subtask2_45.txt,subtask2_46.txt,subtask2_47.txt,subtask2_48.txt,subtask2_49.txt,subtask2_50.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 21 ms 9172 KB
sample_02.txt AC 21 ms 11092 KB
sample_03.txt AC 21 ms 11092 KB
subtask1_01.txt AC 23 ms 11148 KB
subtask1_02.txt AC 23 ms 11148 KB
subtask1_03.txt AC 23 ms 9100 KB
subtask1_04.txt AC 23 ms 11148 KB
subtask1_05.txt AC 23 ms 9100 KB
subtask1_06.txt AC 23 ms 9100 KB
subtask1_07.txt AC 23 ms 9100 KB
subtask1_08.txt AC 23 ms 9100 KB
subtask1_09.txt AC 23 ms 9100 KB
subtask1_10.txt AC 23 ms 9100 KB
subtask1_11.txt AC 23 ms 11148 KB
subtask1_12.txt AC 23 ms 9100 KB
subtask1_13.txt AC 22 ms 9100 KB
subtask1_14.txt AC 23 ms 11148 KB
subtask1_15.txt AC 23 ms 11148 KB
subtask1_16.txt AC 23 ms 11148 KB
subtask1_17.txt AC 23 ms 11148 KB
subtask1_18.txt AC 23 ms 9100 KB
subtask1_19.txt AC 23 ms 11148 KB
subtask1_20.txt AC 23 ms 11148 KB
subtask1_21.txt AC 22 ms 9100 KB
subtask1_22.txt AC 23 ms 9100 KB
subtask1_23.txt AC 23 ms 11148 KB
subtask1_24.txt AC 23 ms 9100 KB
subtask1_25.txt AC 23 ms 11148 KB
subtask1_26.txt AC 23 ms 11148 KB
subtask1_27.txt AC 23 ms 11148 KB
subtask1_28.txt AC 23 ms 11148 KB
subtask1_29.txt AC 22 ms 9100 KB
subtask1_30.txt AC 23 ms 11148 KB
subtask1_31.txt AC 23 ms 11148 KB
subtask1_32.txt AC 23 ms 9100 KB
subtask1_33.txt AC 23 ms 11148 KB
subtask1_34.txt AC 23 ms 11148 KB
subtask1_35.txt AC 22 ms 9100 KB
subtask1_36.txt AC 24 ms 11148 KB
subtask1_37.txt AC 20 ms 9172 KB
subtask1_38.txt AC 21 ms 11092 KB
subtask1_39.txt AC 21 ms 9044 KB
subtask1_40.txt AC 21 ms 11092 KB
subtask1_41.txt AC 21 ms 11092 KB
subtask1_42.txt AC 21 ms 9044 KB
subtask2_01.txt AC 150 ms 15816 KB
subtask2_02.txt AC 150 ms 15816 KB
subtask2_03.txt AC 147 ms 13768 KB
subtask2_04.txt AC 146 ms 13768 KB
subtask2_05.txt AC 148 ms 13768 KB
subtask2_06.txt AC 118 ms 13520 KB
subtask2_07.txt AC 93 ms 14688 KB
subtask2_08.txt AC 63 ms 14048 KB
subtask2_09.txt AC 154 ms 15820 KB
subtask2_10.txt AC 138 ms 15276 KB
subtask2_11.txt AC 143 ms 15816 KB
subtask2_12.txt AC 142 ms 15816 KB
subtask2_13.txt AC 144 ms 13768 KB
subtask2_14.txt AC 138 ms 14540 KB
subtask2_15.txt AC 140 ms 15948 KB
subtask2_16.txt AC 136 ms 13772 KB
subtask2_17.txt AC 134 ms 13768 KB
subtask2_18.txt AC 137 ms 15816 KB
subtask2_19.txt AC 113 ms 14540 KB
subtask2_20.txt AC 118 ms 15948 KB
subtask2_21.txt AC 120 ms 13772 KB
subtask2_22.txt AC 121 ms 13772 KB
subtask2_23.txt AC 122 ms 15336 KB
subtask2_24.txt AC 143 ms 13768 KB
subtask2_25.txt AC 143 ms 15816 KB
subtask2_26.txt AC 152 ms 15816 KB
subtask2_27.txt AC 149 ms 15816 KB
subtask2_28.txt AC 150 ms 13768 KB
subtask2_29.txt AC 123 ms 15320 KB
subtask2_30.txt AC 131 ms 13768 KB
subtask2_31.txt AC 136 ms 13768 KB
subtask2_32.txt AC 142 ms 13768 KB
subtask2_33.txt AC 146 ms 13768 KB
subtask2_34.txt AC 128 ms 13768 KB
subtask2_35.txt AC 140 ms 13772 KB
subtask2_36.txt AC 140 ms 13768 KB
subtask2_37.txt AC 144 ms 13768 KB
subtask2_38.txt AC 138 ms 15688 KB
subtask2_39.txt AC 137 ms 16588 KB
subtask2_40.txt AC 117 ms 14540 KB
subtask2_41.txt AC 137 ms 15820 KB
subtask2_42.txt AC 141 ms 15820 KB
subtask2_43.txt AC 154 ms 13768 KB
subtask2_44.txt AC 148 ms 14536 KB
subtask2_45.txt AC 146 ms 15816 KB
subtask2_46.txt AC 123 ms 14540 KB
subtask2_47.txt AC 149 ms 15816 KB
subtask2_48.txt AC 21 ms 11092 KB
subtask2_49.txt AC 21 ms 11092 KB
subtask2_50.txt AC 21 ms 11092 KB