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 |
|
|
|
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 |