Submission #6430786
Source Code Expand
using System; using System.Collections.Generic; using System.Linq; using System.Text; using static System.Console; using static System.Math; namespace AtTest._800problems { class AGC018_C { static void Main(string[] args) { var sw = new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false }; SetOut(sw); Method(args); Out.Flush(); } static void Method(string[] args) { int[] xyz = ReadInts(); int x = xyz[0]; int y = xyz[1]; int z = xyz[2]; long[][] abcs = new long[x + y + z][]; for(int i = 0; i < x + y + z; i++) { abcs[i] = ReadLongs(); } abcs = abcs.OrderBy(a => a[0] - a[1]).ToArray(); PriorityQueue<int> silverQueue = new PriorityQueue<int>(); PriorityQueue<int> goldQueue = new PriorityQueue<int>(); long[] silverSums = new long[x + y + z]; long[] brondSumsL = new long[x + y + z]; long[] brondSumsR = new long[x + y + z]; long[] goldSums = new long[x + y + z]; for(int i = 0; i < y; i++) { silverQueue.Enqueue(abcs[i][1] - abcs[i][2], i); silverSums[i] = abcs[i][1]; if (i > 0) silverSums[i] += silverSums[i - 1]; } for(int i = y; i < y + z; i++) { silverQueue.Enqueue(abcs[i][1] - abcs[i][2], i); silverSums[i] = silverSums[i - 1] + abcs[i][1]; var pair = silverQueue.Dequeue(); silverSums[i] -= abcs[pair.Value][1]; brondSumsL[i] = brondSumsL[i - 1] + abcs[pair.Value][2]; } for(int i = x + y + z - 1; i >= y+z; i--) { goldQueue.Enqueue(abcs[i][0] - abcs[i][2], i); goldSums[i] = abcs[i][0]; if (i + 1 < x + y + z) goldSums[i] += goldSums[i + 1]; } for(int i = y + z - 1; i >= y; i--) { goldQueue.Enqueue(abcs[i][0] - abcs[i][2], i); goldSums[i] = goldSums[i + 1] + abcs[i][0]; var pair = goldQueue.Dequeue(); goldSums[i] -= abcs[pair.Value][0]; brondSumsR[i] = brondSumsR[i + 1] + abcs[pair.Value][2]; } long res = silverSums[y - 1] + goldSums[y] + brondSumsL[y - 1] + brondSumsR[y]; for(int i = y; i < y + z; i++) { res = Max(res, silverSums[i] + goldSums[i + 1] + brondSumsL[i] + brondSumsR[i + 1]); } WriteLine(res); } class PriorityQueue<T> { private readonly List<KeyValuePair<long, T>> list; public int Count { get; private set; } public PriorityQueue() { list = new List<KeyValuePair<long, T>>(); Count = 0; } private void Add(KeyValuePair<long, T> pair) { if (Count == list.Count) { list.Add(pair); } else { list[Count] = pair; } Count++; } private void Swap(int a, int b) { KeyValuePair<long, T> tmp = list[a]; list[a] = list[b]; list[b] = tmp; } public void Enqueue(long key, T value) { Add(new KeyValuePair<long, T>(key, value)); int c = Count - 1; while (c > 0) { int p = (c - 1) / 2; if (list[c].Key >= list[p].Key) break; Swap(p, c); c = p; } } public KeyValuePair<long, T> Top() { return list[0]; } public KeyValuePair<long, T> Dequeue() { KeyValuePair<long, T> pair = list[0]; Count--; if (Count == 0) return pair; list[0] = list[Count]; int p = 0; while (true) { int c1 = p * 2 + 1; int c2 = p * 2 + 2; if (c1 >= Count) break; int c = (c2 >= Count || list[c1].Key < list[c2].Key) ? c1 : c2; if (list[c].Key >= list[p].Key) break; Swap(p, c); p = c; } return pair; } } private static string Read() { return ReadLine(); } private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); } private static int ReadInt() { return int.Parse(Read()); } private static long ReadLong() { return long.Parse(Read()); } private static double ReadDouble() { return double.Parse(Read()); } private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); } private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); } private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); } } }
Submission Info
Submission Time | |
---|---|
Task | C - Coins |
User | MiuraMiuMiu |
Language | C# (Mono 4.6.2.0) |
Score | 800 |
Code Size | 5670 Byte |
Status | AC |
Exec Time | 354 ms |
Memory | 35132 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 30 ms | 11732 KB |
sample_02.txt | AC | 28 ms | 11604 KB |
sample_03.txt | AC | 28 ms | 11604 KB |
subtask_1_01.txt | AC | 28 ms | 11604 KB |
subtask_1_02.txt | AC | 79 ms | 20060 KB |
subtask_1_03.txt | AC | 93 ms | 19924 KB |
subtask_1_04.txt | AC | 173 ms | 23756 KB |
subtask_1_05.txt | AC | 204 ms | 25032 KB |
subtask_1_06.txt | AC | 246 ms | 30400 KB |
subtask_1_07.txt | AC | 89 ms | 19800 KB |
subtask_1_08.txt | AC | 301 ms | 28608 KB |
subtask_1_09.txt | AC | 79 ms | 19160 KB |
subtask_1_10.txt | AC | 202 ms | 30276 KB |
subtask_1_11.txt | AC | 276 ms | 31668 KB |
subtask_1_12.txt | AC | 226 ms | 29236 KB |
subtask_1_13.txt | AC | 275 ms | 31796 KB |
subtask_1_14.txt | AC | 348 ms | 31540 KB |
subtask_1_15.txt | AC | 315 ms | 33204 KB |
subtask_1_16.txt | AC | 311 ms | 31548 KB |
subtask_1_17.txt | AC | 330 ms | 35132 KB |
subtask_1_18.txt | AC | 354 ms | 34876 KB |
subtask_1_19.txt | AC | 316 ms | 29116 KB |
subtask_1_20.txt | AC | 279 ms | 29492 KB |
subtask_1_21.txt | AC | 228 ms | 31668 KB |
subtask_1_22.txt | AC | 271 ms | 31412 KB |
subtask_1_23.txt | AC | 314 ms | 33588 KB |
subtask_1_24.txt | AC | 317 ms | 29108 KB |
subtask_1_25.txt | AC | 275 ms | 31548 KB |
subtask_1_26.txt | AC | 297 ms | 32188 KB |
subtask_1_27.txt | AC | 335 ms | 33468 KB |
subtask_1_28.txt | AC | 315 ms | 31164 KB |
subtask_1_29.txt | AC | 28 ms | 11604 KB |