結果
| 問題 |
No.949 飲酒プログラミングコンテスト
|
| コンテスト | |
| ユーザー |
 eSeF
|
| 提出日時 | 2020-01-22 01:53:34 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,003 bytes |
| コンパイル時間 | 893 ms |
| コンパイル使用メモリ | 113,536 KB |
| 実行使用メモリ | 91,872 KB |
| 最終ジャッジ日時 | 2024-07-06 15:34:37 |
| 合計ジャッジ時間 | 10,691 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 14 WA * 15 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Math;
using static System.Array;
using static AtCoder.Tool;
using static AtCoder.CalcL;
namespace AtCoder
{
class AC
{
const int MOD = 1000000007;
const int INF = int.MaxValue / 2;
const long SINF = long.MaxValue / 2;
const double EPS = 1e-8;
static readonly int[] dI = { 0, 1, 0, -1 };
static readonly int[] dJ = { 1, 0, -1, 0 };
static List<List<int>> G = new List<List<int>>();
//static List<List<Edge>>G = new List<List<Edge>>();
//static List<Edge> E = new List<Edge>();
static void Main(string[] args)
{
//var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
//Console.SetOut(sw);
var cin = new Scanner();
int N = int.Parse(Console.ReadLine());
var A = cin.ReadSplitInt();
var B = cin.ReadSplitInt();
var D = cin.ReadSplitInt();
Sort(D, (x, y) => (y - x));
var dp = new int[N + 1][];
var prev = new int[N + 1][];
for(var i = 0; i <= N; i++)
{
dp[i] = new int[N + 1];
prev[i] = new int[N + 1];
Initialize(ref dp[i], 0);
Initialize(ref prev[i], -1);
}
int l = -1;
int r = N;
for(var i = 0; i <= N; i++)
{
for(var j = 0; j <= N; j++)
{
if (i + j > N) continue;
l = -1;r = N;
int cap = A[i] + B[j];
while (r - l > 1)
{
int mid = (l + r) / 2;
if (D[mid] > cap) { l = mid; }
else { r = mid; }
}
if (i > 0 && prev[i - 1][j] < N - 1)
{
int nx = dp[i - 1][j] + (r != N ? 1 : 0);
if (nx > dp[i][j])
{
dp[i][j] = nx;
prev[i][j] = Max(prev[i - 1][j] + 1, r);
}
}
if (j > 0 && prev[i][j - 1] < N - 1)
{
int nx = dp[i][j - 1] + (r != N ? 1 : 0);
if (nx == dp[i][j])
{
prev[i][j] = Min(prev[i][j], Max(prev[i][j - 1], r));
}
if (nx > dp[i][j])
{
dp[i][j] = nx;
prev[i][j] = Max(prev[i][j - 1] + 1, r);
}
}
}
}
/*foreach(var d in dp)
{
Console.WriteLine(string.Join(" ", d));
}*/
Console.WriteLine(dp.Max(x => x.Max()));
//Console.Out.Flush();
}
struct Edge
{
public int from;
public int to;
public long dist;
public Edge(int t, long c)
{
from = -1;
to = t;
dist = c;
}
public Edge(int f, int t, long c)
{
from = f;
to = t;
dist = c;
}
}
}
public class Scanner
{
public int[] ReadSplitInt()
{
return ConvertAll(Console.ReadLine().Split(), int.Parse);
}
public long[] ReadSplitLong()
{
return ConvertAll(Console.ReadLine().Split(), long.Parse);
}
public double[] ReadSplit_Double()
{
return ConvertAll(Console.ReadLine().Split(), double.Parse);
}
}
public static class Tool
{
static public void Initialize<T>(ref T[] array, T initialvalue)
{
for (var i = 0; i < array.Length; i++)
{
array[i] = initialvalue;
}
}
static public void Swap<T>(ref T a, ref T b)
{
T keep = a;
a = b;
b = keep;
}
static public void Display<T>(T[,] array2d, int n, int m)
{
for (var i = 0; i < n; i++)
{
for (var j = 0; j < m; j++)
{
Console.Write($"{array2d[i, j]} ");
}
Console.WriteLine();
}
}
static public long LPow(int a, int b)
{
return (long)Pow(a, b);
}
}
static public class CalcI
{
public static int Gcd(int a, int b)
{
if (a * b == 0) { return Max(a, b); }
return a % b == 0 ? b : Gcd(b, a % b);
}
public static int Lcm(int a, int b)
{
int g = Gcd(a, b);
return a / g * b;
}
public static int Ceil(int n, int div)
{
return (n + div - 1) / div;
}
}
static public class CalcL
{
public static long Gcd(long a, long b)
{
if (a * b == 0) { return Max(a, b); }
return a % b == 0 ? b : Gcd(b, a % b);
}
public static long Lcm(long a, long b)
{
long g = Gcd(a, b);
return a / g * b;
}
public static long Ceil(long n, long div)
{
return (n + div - 1) / div;
}
}
class Modulo
{
private const int M = 1000000007;
private readonly int[] m_facs;
public int Mul(int a, int b)
{
return (int)(Math.BigMul(a, b) % M);
}
public Modulo(int n)
{
m_facs = new int[n + 1];
m_facs[0] = 1;
for (int i = 1; i <= n; ++i)
{
m_facs[i] = Mul(m_facs[i - 1], i);
}
}
public int Fac(int n)
{
return m_facs[n];
}
public int Pow(int a, int m)
{
switch (m)
{
case 0:
return 1;
case 1:
return a;
default:
int p1 = Pow(a, m / 2);
int p2 = Mul(p1, p1);
return ((m % 2) == 0) ? p2 : Mul(p2, a);
}
}
public int Div(int a, int b)
{
return Mul(a, Pow(b, M - 2));
}
public int Ncr(int n, int r)
{
if (n < r) { return 0; }
if (n == r) { return 1; }
int res = Fac(n);
res = Div(res, Fac(r));
res = Div(res, Fac(n - r));
return res;
}
public Modulo() { }
}
}