結果
| 問題 |
No.1708 Quality of Contest
|
| コンテスト | |
| ユーザー |
 kakel-san
|
| 提出日時 | 2023-12-26 00:28:09 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 1,273 ms / 2,000 ms |
| コード長 | 13,102 bytes |
| コンパイル時間 | 9,384 ms |
| コンパイル使用メモリ | 167,600 KB |
| 実行使用メモリ | 241,600 KB |
| 最終ジャッジ日時 | 2024-09-27 14:49:32 |
| 合計ジャッジ時間 | 31,943 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (100 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
class Program
{
static int NN => int.Parse(ReadLine());
static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
public static void Main()
{
Solve();
// Test();
}
static void Test()
{
var r = new Random();
var count = 0;
while (true)
{
var n = 4;
var m = n;
var x = r.Next(10);
var map = new int[n][];
for (var i = 0; i < n; ++i) map[i] = new int[] { r.Next(10), r.Next(m) + 1 };
var k = 1;
var c = new int[k];
for (var i = 0; i < k; ++i) c[i] = r.Next(n + 1);
// 愚直解
var s1 = All(n, m, x, map, k, c);
// 作成解
var s2 = Contest(n, m, x, map, k, c);
if (s1 != s2)
{
WriteLine($"{n} {m} {x} {k}");
WriteLine(string.Join("\n", map.Select(m => string.Join(" ", m))));
WriteLine(string.Join(" ", c));
WriteLine(s1);
WriteLine(s2);
return;
}
++count;
if (count % 1000 == 0) WriteLine(count);
}
}
static long All(int n, int m, int x, int[][] map, int k, int[] c)
{
var ans = 0L;
Permutate(n, list =>
{
var pts = 0L;
foreach (var ci in c)
{
var gset = new HashSet<int>();
for (var i = 0; i < ci; ++i)
{
pts += map[list[i]][0];
gset.Add(map[list[i]][1]);
}
pts += gset.Count * (long)x;
}
ans = Math.Max(ans, pts);
});
return ans;
}
static void Permutate(int n, Action<int[]> action)
{
var seed = new int[n];
for (var i = 0; i < n; ++i) seed[i] = i;
var used = new bool[n];
var perm = new int[n];
Permutate(0, seed, perm, used, action);
}
static void Permutate(int pos, int[] seed, int[] perm, bool[] used, Action<int[]> action)
{
if (pos == used.Length) action(perm);
for (var i = 0; i < used.Length; ++i)
{
if (used[i]) continue;
perm[pos] = seed[i];
used[i] = true;
Permutate(pos + 1, seed, perm, used, action);
used[i] = false;
}
}
static void Solve()
{
var c = NList;
var (n, m, x) = (c[0], c[1], c[2]);
var map = NArr(n);
var k = NN;
c = NList;
WriteLine(Contest(n, m, x, map, k, c));
}
static long Contest(int n, int m, int x, int[][] map, int k, int[] c)
{
var counts = new int[n];
foreach (var ci in c) if (ci > 0) ++counts[ci - 1];
for (var i = counts.Length - 2; i >= 0; --i) counts[i] += counts[i + 1];
var glist = new List<Pair>[m];
for (var i = 0; i < glist.Length; ++i) glist[i] = new List<Pair>();
foreach (var p in map) glist[p[1] - 1].Add(new Pair(p[1] - 1, p[0]));
for (var i = 0; i < glist.Length; ++i) glist[i].Sort((l, r) => r.Value.CompareTo(l.Value));
var tree = new AvlTree<Pair>();
for (var g = 0; g < glist.Length; ++g) foreach (var v in glist[g]) tree.Insert(v);
var tree2 = new PriorityQueue<int, int>();
var ans = 0L;
for (var i = 0; i < n; ++i)
{
if (tree.GetCount() > 0 && tree2.Count > 0)
{
var newpeek = tree.ElementAt(tree.GetCount() - 1);
var newv = x + newpeek.Value;
var oldv = tree2.Peek();
if (newv > oldv)
{
ans += (long)counts[i] * newv;
tree.Delete(newpeek);
for (var j = 1; j < glist[newpeek.Genre].Count; ++j)
{
tree.Delete(glist[newpeek.Genre][j]);
tree2.Enqueue(glist[newpeek.Genre][j].Value, - glist[newpeek.Genre][j].Value);
}
}
else
{
ans += (long)counts[i] * tree2.Dequeue();
}
}
else if (tree.GetCount() > 0)
{
var newpeek = tree.ElementAt(tree.GetCount() - 1);
ans += (long)counts[i] * (x + newpeek.Value);
tree.Delete(newpeek);
for (var j = 1; j < glist[newpeek.Genre].Count; ++j)
{
tree.Delete(glist[newpeek.Genre][j]);
tree2.Enqueue(glist[newpeek.Genre][j].Value, - glist[newpeek.Genre][j].Value);
}
}
else
{
ans += (long)counts[i] * tree2.Dequeue();
}
}
return ans;
}
public class Pair : IComparable<Pair>
{
public int Genre;
public int Value;
public Pair(int g, int v)
{
Genre = g;
Value = v;
}
int IComparable<Pair>.CompareTo(Pair other)
{
var d = Value.CompareTo(other.Value);
if (d != 0) return d;
return Genre.CompareTo(other.Genre);
}
}
public class AvlTree<T> where T: IComparable<T>
{
private class Node<U> where U: IComparable<U>
{
public U Value;
public Node<U> Lc = null;
public Node<U> Rc = null;
public int Height;
public int Count;
public int CCount;
public Node(int height, U value)
{
Height = height;
Count = 1;
CCount = 1;
Value = value;
}
}
private Node<T> root = null;
static int GetHeight(Node<T> t)
{
return t == null ? 0 : t.Height;
}
static int GetCount(Node<T> t)
{
return t == null ? 0 : t.Count;
}
static int GetBalance(Node<T> t)
{
return GetHeight(t.Lc) - GetHeight(t.Rc);
}
static void Recalc(Node<T> t)
{
if (t == null) return;
t.Height = 1 + Math.Max(GetHeight(t.Lc), GetHeight(t.Rc));
t.Count = t.CCount + GetCount(t.Lc) + GetCount(t.Rc);
}
static Node<T> RotateLeft(Node<T> t)
{
Node<T> u = t.Rc;
Node<T> t2 = u.Lc;
u.Lc = t;
t.Rc = t2;
Recalc(t);
Recalc(u);
return u;
}
static Node<T> RotateRight(Node<T> t)
{
Node<T> u = t.Lc;
Node<T> t2 = u.Rc;
u.Rc = t;
t.Lc = t2;
Recalc(t);
Recalc(u);
return u;
}
static Node<T> RotateLR(Node<T> t)
{
t.Lc = RotateLeft(t.Lc);
return RotateRight(t);
}
static Node<T> RotateRL(Node<T> t)
{
t.Rc = RotateRight(t.Rc);
return RotateLeft(t);
}
static Node<T> BalanceLeft(Node<T> t)
{
if (GetBalance(t) > 1)
{
if (GetBalance(t.Lc) < 0) t = RotateLR(t);
else t = RotateRight(t);
}
Recalc(t);
return t;
}
static Node<T> BalanceRight(Node<T> t)
{
if (GetBalance(t) < -1)
{
if (GetBalance(t.Rc) > 0) t = RotateRL(t);
else t = RotateLeft(t);
}
Recalc(t);
return t;
}
/// <summary>valueを挿入する</summary>
public void Insert(T value)
{
root = Insert(root, value);
}
Node<T> Insert(Node<T> cur, T value)
{
if (cur == null)
{
return new Node<T>(1, value);
}
var d = value.CompareTo(cur.Value);
if (d < 0)
{
cur.Lc = Insert(cur.Lc, value);
return BalanceLeft(cur);
}
else if (d > 0)
{
cur.Rc = Insert(cur.Rc, value);
return BalanceRight(cur);
}
else
{
++cur.CCount;
Recalc(cur);
return cur;
}
}
/// <summary>valueを削除する 存在しない場合はなにもしない</summary>
public void Delete(T value)
{
root = Delete(root, value);
}
Node<T> Delete(Node<T> cur, T value)
{
if (cur == null) return null;
var d = value.CompareTo(cur.Value);
if (d < 0)
{
cur.Lc = Delete(cur.Lc, value);
return BalanceRight(cur);
}
else if (d > 0)
{
cur.Rc = Delete(cur.Rc, value);
return BalanceLeft(cur);
}
else
{
--cur.CCount;
if (cur.CCount == 0)
{
if (cur.Lc != null)
{
Node<T> del = null;
var max = DeleteMax(cur.Lc, ref del);
cur.Lc = max;
cur.Value = del.Value;
cur.CCount = del.CCount;
return BalanceRight(cur);
}
else
{
return cur.Rc;
}
}
else
{
Recalc(cur);
return cur;
}
}
}
Node<T> DeleteMax(Node<T> t, ref Node<T> del)
{
if (t.Rc == null)
{
del = t;
return t.Lc;
}
else
{
var max = DeleteMax(t.Rc, ref del);
t.Rc = max;
return BalanceLeft(t);
}
}
/// <summary>小さいほうからpos番目の要素を取得する</summary>
public T ElementAt(int pos)
{
if (pos < 0 || pos >= GetCount(root)) return default;
var t = ElementAt(root, pos);
return t.Value;
}
/// <summary>小さいほうからpos番目の要素を取得する</summary>
public T ElementAt(int pos, T defaultValue)
{
if (pos < 0 || pos >= GetCount(root)) return defaultValue;
return ElementAt(pos);
}
Node<T> ElementAt(Node<T> cur, int pos)
{
if (pos < GetCount(cur.Lc)) return ElementAt(cur.Lc, pos);
if (pos < GetCount(cur.Lc) + cur.CCount) return cur;
if (pos < cur.Count) return ElementAt(cur.Rc, pos - GetCount(cur.Lc) - cur.CCount);
return null;
}
public void Debug()
{
if (root == null) return;
Console.WriteLine($"root val:{root.Value}, CCount:{root.CCount}, Count:{root.Count}");
Debug(root.Value, root.Lc);
Debug(root.Value, root.Rc);
}
void Debug(T pval, Node<T> cur)
{
if (cur == null) return;
Console.WriteLine($"{pval} -> val:{cur.Value}, CCount:{cur.CCount}, Count:{cur.Count}");
Debug(cur.Value, cur.Lc);
Debug(cur.Value, cur.Rc);
}
/// <summary>value以上でもっとも小さい値とその場所を返却する</summary>
public T LowerBound(T value, ref int index)
{
var cur = root;
T ans = default;
var add = 0;
index = GetCount(root);
while (cur != null)
{
if (value.CompareTo(cur.Value) <= 0)
{
ans = cur.Value;
index = add + GetCount(cur.Lc);
cur = cur.Lc;
}
else
{
add += GetCount(cur.Lc) + cur.CCount;
cur = cur.Rc;
}
}
return ans;
}
/// <summary>要素の個数を求める</summary>
public int GetCount()
{
return GetCount(root);
}
}
}