Submission #1258560


Source Code Expand

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 Info

Submission Time
Task E - 花火
User leign
Language C# (Mono 4.6.2.0)
Score 160
Code Size 3070 Byte
Status AC
Exec Time 154 ms
Memory 16588 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 130 / 130
Status
AC × 3
AC × 45
AC × 95
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 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 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
Case Name Status Exec Time Memory
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