結果

問題 No.2730 Two Types Luggage
ユーザー beyanon
提出日時 2024-04-19 21:46:44
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,100 ms / 2,000 ms
コード長 22,924 bytes
コンパイル時間 8,078 ms
コンパイル使用メモリ 168,484 KB
実行使用メモリ 425,524 KB
最終ジャッジ日時 2024-10-11 14:41:30
合計ジャッジ時間 25,120 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (95 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/

ソースコード

diff #
プレゼンテーションモードにする

#pragma warning disable
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using static System.Console;
using static System.Math;
using static Util;
using System.Security.Cryptography;
#region using(AtCoder)
// using pii = (int, int);
// using pll = (long, long);
// using pdd = (double, double);
// using pss = (string, string);
// using pis = (int, string);
// using psi = (string, int);
// using pls = (long, string);
// using psl = (string, long);
// using pds = (double, string);
// using psd = (string, double);
// using pid = (int, double);
// using pdi = (double, int);
// using pld = (long, double);
// using pdl = (double, long);
// using vb = bool[];
// using vvb = bool[][];
// using vvvb = bool[][][];
// using vi = int[];
// using vvi = int[][];
// using vvvi = int[][][];
// using vl = long[];
// using vvl = long[][];
// using vvvl = long[][][];
// using vd = double[];
// using vvd = double[][];
// using vvvd = double[][][];
// using vs = string[];
// using vvs = string[][];
// using vvvs = string[][][];
// using listb = System.Collections.Generic.List<bool>;
// using llistb = System.Collections.Generic.List<System.Collections.Generic.List<bool>>;
// using lllistb = System.Collections.Generic.List<System.Collections.Generic.List<System.Collections.Generic.List<bool>>>;
// using listi = System.Collections.Generic.List<int>;
// using llisti = System.Collections.Generic.List<System.Collections.Generic.List<int>>;
// using lllisti = System.Collections.Generic.List<System.Collections.Generic.List<System.Collections.Generic.List<int>>>;
// using listl = System.Collections.Generic.List<long>;
// using llistl = System.Collections.Generic.List<System.Collections.Generic.List<long>>;
// using lllistl = System.Collections.Generic.List<System.Collections.Generic.List<System.Collections.Generic.List<long>>>;
// using listd = System.Collections.Generic.List<double>;
// using llistd = System.Collections.Generic.List<System.Collections.Generic.List<double>>;
// using lllistd = System.Collections.Generic.List<System.Collections.Generic.List<System.Collections.Generic.List<double>>>;
// using lists = System.Collections.Generic.List<string>;
// using llists = System.Collections.Generic.List<System.Collections.Generic.List<string>>;
// using lllists = System.Collections.Generic.List<System.Collections.Generic.List<System.Collections.Generic.List<string>>>;
// using mii = System.Collections.Generic.SortedDictionary<int, int>;
// using mll = System.Collections.Generic.SortedDictionary<long, long>;
// using mss = System.Collections.Generic.SortedDictionary<string, string>;
// using mis = System.Collections.Generic.SortedDictionary<int, string>;
// using msi = System.Collections.Generic.SortedDictionary<string, int>;
// using mls = System.Collections.Generic.SortedDictionary<long, string>;
// using msl = System.Collections.Generic.SortedDictionary<string, long>;
// using umii = System.Collections.Generic.Dictionary<int, int>;
// using umll = System.Collections.Generic.Dictionary<long, long>;
// using umss = System.Collections.Generic.Dictionary<string, string>;
// using umis = System.Collections.Generic.Dictionary<int, string>;
// using umsi = System.Collections.Generic.Dictionary<string, int>;
// using umls = System.Collections.Generic.Dictionary<long, string>;
// using umsl = System.Collections.Generic.Dictionary<string, long>;
// using seti = System.Collections.Generic.SortedSet<int>;
// using setl = System.Collections.Generic.SortedSet<long>;
// using sets = System.Collections.Generic.SortedSet<string>;
// using useti = System.Collections.Generic.HashSet<int>;
// using usetl = System.Collections.Generic.HashSet<long>;
// using usets = System.Collections.Generic.HashSet<string>;
#endregion
class Util {
public static double PI = 3.141592653589793;
public static long m107 = 1000000007;
public static long m998 = 998244353;
public static int a10_9 = 1000000000;
public static long a10_18 = 1000000000000000000;
public static int iinf = 1 << 31;
public static long linf = (1l << 61) - (1l << 31);
/// <summary>1</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static string read() => ReadLine();
/// <summary>1</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static string readln() => ReadLine();
/// <summary>1</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static string readline() => ReadLine();
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void write() => Write("");
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void write<T>(T value) => Write(value);
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void writeln() => WriteLine("");
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void writeln<T>(T value) => WriteLine(value);
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void writeline() => WriteLine("");
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void writeline<T>(T value) => WriteLine(value);
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void print() => Write("");
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void print<T>(T value) => Write(value);
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void println() => WriteLine("");
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void println<T>(T value) => WriteLine(value);
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void printline() => WriteLine("");
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void printline<T>(T value) => WriteLine(value);
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T[] makearr<T>(int num, T value) {
var arr = new T[num];
for (int i = 0; i < num; ++i) arr[i] = value;
return arr;
} // end of func
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T[][] makearr2<T>(int height, int width, T value) {
var arr = new T[height][];
for (int i = 0; i < height; ++i) {
arr[i] = new T[width];
for (int j = 0; j < width; ++j) {
arr[i][j] = value;
}
}
return arr;
} // end of func
/// <summary>3</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T[][][] makearr3<T>(int height, int width, int depth, T value) {
var arr = new T[height][][];
for (int i = 0; i < height; ++i) {
arr[i] = new T[width][];
for (int j = 0; j < width; ++j) {
arr[i][j] = new T[depth];
for (int k = 0; k < depth; ++k) {
arr[i][j][k] = value;
}
}
}
return arr;
} // end of func
/// <summary>List</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static List<T> makelist<T>(int num, T value) {
return new List<T>(makearr(num, value));
} // end of func
/// <summary>2List</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static List<List<T>> makelist2<T>(int height, int width, T value) {
var arr = new List<List<T>>();
for (int i = 0; i < height; ++i) {
arr.Add(makelist(width, value));
}
return arr;
} // end of func
/// <summary>3List</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static List<List<List<T>>> makelist3<T>(int height, int width, int depth, T value) {
var arr = new List<List<List<T>>>();
for (int i = 0; i < height; ++i) {
arr[i] = new List<List<T>>();
for (int j = 0; j < width; ++j) {
arr[i].Add(makelist(depth, value));
}
}
return arr;
} // end of func
/// <summary>1</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T[] copyarr<T>(T[] arr) {
T[] brr = new T[arr.Length];
Array.Copy(arr, brr, arr.Length);
return brr;
} // end of func
/// <summary>2</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T[][] copyarr2<T>(T[][] arr) {
T[][] brr = new T[arr.Length][];
for (int i = 0; i < arr.Length; ++i) {
brr[i] = new T[arr[i].Length];
Array.Copy(arr[i], brr[i], arr[i].Length);
}
return brr;
} // end of func
/// <summary>3</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T[][][] copyarr3<T>(T[][][] arr) {
T[][][] brr = new T[arr.Length][][];
for (int i = 0; i < arr.Length; ++i) {
brr[i] = new T[arr[i].Length][];
for (int j = 0; j < arr[i].Length; ++j) {
brr[i][j] = new T[arr[i][j].Length];
Array.Copy(arr[i][j], brr[i][j], arr[i][j].Length);
}
}
return brr;
} // end of func
/// <summary>1List</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static List<T> copylist<T>(List<T> list) {
return new List<T>(list);
} // end of func
/// <summary>2List</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static List<List<T>> copylist2<T>(List<List<T>> list) {
List<List<T>> list2 = new List<List<T>>();
for (int i = 0; i < list.Count; ++i) {
list2.Add(new List<T>(list[i]));
}
return list2;
} // end of func
/// <summary>3List</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static List<List<List<T>>> copylist3<T>(List<List<List<T>>> list) {
List<List<List<T>>> list2 = new List<List<List<T>>>();
for (int i = 0; i < list.Count; ++i) {
List<List<T>> tmplist = new List<List<T>>();
for (int j = 0; j < list[i].Count; ++i) {
tmplist.Add(new List<T>(list[i][j]));
}
list2.Add(tmplist);
}
return list2;
} // end of func
/// <summary>1List</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void printlist<T>(List<T> list) {
WriteLine(string.Join(" ", list));
} // end of func
/// <summary>1</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void printlist<T>(T[] list) {
WriteLine(string.Join(" ", list));
} // end of func
/// <summary>2</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void printlist2<T>(List<List<T>> list) {
foreach (var l in list) {
WriteLine(string.Join(" ", l));
}
} // end of func
/// <summary>2</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void printlist2<T>(T[][] list) {
foreach (var l in list) {
WriteLine(string.Join(" ", l));
}
} // end of func
/// <summary>1List</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void printarr<T>(List<T> list) {
WriteLine(string.Join(" ", list));
} // end of func
/// <summary>1</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void printarr<T>(T[] list) {
WriteLine(string.Join(" ", list));
} // end of func
/// <summary>2</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void printarr2<T>(List<List<T>> list) {
foreach (var l in list) {
WriteLine(string.Join(" ", l));
}
} // end of func
/// <summary>2</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void printarr2<T>(T[][] list) {
foreach (var l in list) {
WriteLine(string.Join(" ", l));
}
} // end of func
/// <summary>1int</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int readint() {
return int.Parse(ReadLine());
} // end of func
/// <summary>1long</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static long readlong() {
return long.Parse(ReadLine());
} // end of func
/// <summary>string()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static string[] readsplit() {
return ReadLine().Split(' ');
} // end of func
/// <summary>int</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int[] readints() {
return ReadLine().Split(' ').Select(_ => int.Parse(_)).ToArray();
} // end of func
/// <summary>long</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static long[] readlongs() {
return ReadLine().Split(' ').Select(_ => long.Parse(_)).ToArray();
} // end of func
/// <summary>float</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static float[] readfloats() {
return ReadLine().Split(' ').Select(_ => float.Parse(_)).ToArray();
} // end of func
/// <summary>double</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static double[] readdoubles() {
return ReadLine().Split(' ').Select(_ => double.Parse(_)).ToArray();
} // end of func
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static string[] readstrings() {
return ReadLine().Split(' ');
} // end of func
/// <summary>int2()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (int, int) readintt2() {
var arr = readints();
return (arr[0], arr[1]);
} // end of func
/// <summary>int3()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (int, int, int) readintt3() {
var arr = readints();
return (arr[0], arr[1], arr[2]);
} // end of func
/// <summary>int4()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (int, int, int, int) readintt4() {
var arr = readints();
return (arr[0], arr[1], arr[2], arr[3]);
} // end of func
/// <summary>long2()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (long, long) readlongt2() {
var arr = readlongs();
return (arr[0], arr[1]);
} // end of func
/// <summary>long3()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (long, long, long) readlongt3() {
var arr = readlongs();
return (arr[0], arr[1], arr[2]);
} // end of func
/// <summary>long4()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (long, long, long, long) readlongt4() {
var arr = readlongs();
return (arr[0], arr[1], arr[2], arr[3]);
} // end of func
/// <summary>float2()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (float, float) readfloatt2() {
var arr = readfloats();
return (arr[0], arr[1]);
} // end of func
/// <summary>float3()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (float, float, float) readfloatt3() {
var arr = readfloats();
return (arr[0], arr[1], arr[2]);
} // end of func
/// <summary>float4()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (float, float, float, float) readfloatt4() {
var arr = readfloats();
return (arr[0], arr[1], arr[2], arr[3]);
} // end of func
/// <summary>double2()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (double, double) readdoublet2() {
var arr = readdoubles();
return (arr[0], arr[1]);
} // end of func
/// <summary>double3()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (double, double, double) readdoublet3() {
var arr = readdoubles();
return (arr[0], arr[1], arr[2]);
} // end of func
/// <summary>double4()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (double, double, double, double) readdoublet4() {
var arr = readdoubles();
return (arr[0], arr[1], arr[2], arr[3]);
} // end of func
/// <summary>string2()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (string, string) readstringt2() {
var arr = ReadLine().Split(' ');
return (arr[0], arr[1]);
} // end of func
/// <summary>string3()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (string, string, string) readstringt3() {
var arr = ReadLine().Split(' ');
return (arr[0], arr[1], arr[2]);
} // end of func
/// <summary>string3()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (string, string, string, string) readstringt4() {
var arr = ReadLine().Split(' ');
return (arr[0], arr[1], arr[2], arr[3]);
} // end of func
/// <summary>(int)1</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (int, long) readintlongt2() {
var arr = ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
return ((int)arr[0], arr[1]);
} // end of func
/// <summary>(int)2</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (int, long, long) readintlongt3() {
var arr = ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
return ((int)arr[0], arr[1], arr[2]);
} // end of func
/// <summary>(int)2</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static (int, long, long, long) readintlongt4() {
var arr = ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
return ((int)arr[0], arr[1], arr[2], arr[3]);
} // end of func
/// <summary>16()</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void WriteLine16<T>(T num) {
WriteLine(string.Format("{0:0.################}", num));
} // end of func
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void WriteLine2bit(int num) {
WriteLine(Convert.ToString(num, 2));
} // end of func
/// <summary></summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void WriteLine2bit(long num) {
WriteLine(Convert.ToString(num, 2));
} // end of func
/// <summary>2</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static string IntToString2bit(int num) {
return Convert.ToString(num, 2);
} // end of func
/// <summary>2</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static string LongToString2bit(long num) {
return Convert.ToString(num, 2);
} // end of func
/// <summary>flush</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void preprocess() {
var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
System.Console.SetOut(sw);
} // end of func
/// <summary>flush</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void finalprocess() {
System.Console.Out.Flush();
} // end of func
} // end of class
/// 便(16bytestruct)
struct YX {
public int y;
public int x;
public YX(int y, int x) {
this.y = y;
this.x = x;
}
} // end of class
/// (16bytestruct)
struct Edge {
public int from;
public int to;
public long cost;
public Edge(int from, int to, long cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
} // end of class
class Kyopuro {
public static void Main() {
preprocess();
var kyopuro = new Kyopuro();
kyopuro.Solve();
finalprocess();
} // end of func
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Solve() {
var (nn, mm, w) = readlongt3();
int n = (int)nn;
int m = (int)mm;
var arr = readlongs();
var brr = readlongs();
var crr = readlongs();
var dp = new Dictionary<long, long>[m + 1];
for (int i = 0; i <= m; ++i) dp[i] = new Dictionary<long, long>();
dp[0][0] = 0;
for (int i = 0; i < m; ++i) {
foreach (var kv in dp[i]) {
long key = kv.Key;
long val = kv.Value;
long nextkey = key + brr[i];
long nextval = val + crr[i];
if (dp[i + 1].ContainsKey(key) == false) {
dp[i + 1][key] = val;
} else {
dp[i + 1][key] = Max(dp[i + 1][key], val);
}
if (dp[i + 1].ContainsKey(nextkey) == false) {
dp[i + 1][nextkey] = nextval;
} else {
dp[i + 1][nextkey] = Max(dp[i + 1][nextkey], nextval);
}
}
}
Array.Sort(arr);
Array.Reverse(arr);
var pref = new long[n + 1];
for (int i = 0; i < n; ++i) {
pref[i + 1] = pref[i] + arr[i];
}
long ans = 0;
long k, v;
foreach (var kv in dp.Last()) {
k = kv.Key;
v = kv.Value;
if (k > w) continue;
if (w - k > n) {
v += pref[n];
} else if (w - k >= 0) {
v += pref[w - k];
}
ans = Max(ans, v);
}
writeline(ans);
} // end of method
} // end of class
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0