結果
| 問題 | No.2232 Miser's Gift |
| ユーザー |
 Asahi
|
| 提出日時 | 2023-03-03 23:05:38 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 540 ms / 2,000 ms |
| コード長 | 6,403 bytes |
| コンパイル時間 | 3,313 ms |
| コンパイル使用メモリ | 90,060 KB |
| 実行使用メモリ | 218,412 KB |
| 最終ジャッジ日時 | 2024-09-18 00:15:53 |
| 合計ジャッジ時間 | 24,968 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 55 |
ソースコード
import java.util.*;
import java.io.*;
import java.math.*;
import java.util.regex.Pattern;
class Main{
static void solve(){
int N = ni(), W = ni();
long [][] dp = new long[N+1][W+1];
long [][] ct = new long[N+1][W+1];
int [] w = new int[N];
long [] v = new long[N];
ct[0][0] = 1;
for(int i=0;i<N;i++) {
w[i] = ni();
v[i] = nl();
}
for(int i=0;i<N;i++) {
for(int j=0;j<=W;j++){
dp[i+1][j] = Math.max(dp[i+1][j],dp[i][j]);
if(j + w[i] <= W) dp[i+1][j+w[i]] = Math.max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
}
}
long base = dp[N][W] + 1;
for(int i=1;i<=W;i++) {
output.println(base-dp[N][W-i]);
}
}
/* 関数 */
/* 定数 */
static PrintWriter output;
static Scanner sc;
static int Inf = 1010101010;
static long Lnf = (long)1e18;
static final long mod = 1000000007;
static final long MOD = 998244353 ;
/* 長いやつ */
static String cut(String S , int start, int end) { return S.substring(start,end);}
static char cut(String S , int start) { return S.charAt(start);}
static String tos(int val) { return Integer.toString(val);}
static String tos(long val) { return Long.toString(val);}
static int toi(String S) { return Integer.parseInt(S);}
static long tol(String S) { return Long.parseLong(S);}
/* 実装が面倒なやつ */
public static long factorial(long n){
return n <= 0 ? 1 : n * factorial(n-1);
}
public static int digits(long n) {
return String.valueOf(n).length();
}
static boolean kaibun(String S) {
StringBuilder s = new StringBuilder();
s.append(S);
return s.reverse().toString().equals(S);
}
static boolean isNumber(String value) {
boolean result = false;
if (value != null) {
Pattern pattern = Pattern.compile("^[0-9]+$|-[0-9]+$");
result = pattern.matcher(value).matches();
}
return result;
}
static Map<Integer,Integer> counter(int [] A) {
HashMap<Integer,Integer> count = new HashMap<>();
for(int i=0;i<A.length;i++) {
if(!count.containsKey(A[i])) count.put(A[i],1);
else count.put(A[i],count.get(A[i])+1);
}
return count;
}
static Map<Long,Integer> counter(long [] A) {
HashMap<Long,Integer> count = new HashMap<>();
for(int i=0;i<A.length;i++) {
if(!count.containsKey(A[i])) count.put(A[i],1);
else count.put(A[i],count.get(A[i])+1);
}
return count;
}
/*入出力端折るやつ*/
static int ni(){ return Integer.parseInt(sc.next());}
static long nl(){ return Long.parseLong(sc.next());}
static double nd(){ return Double.parseDouble(sc.next());}
static String ns(){ return sc.next();}
static BigInteger bi(){ return sc.nextBigInteger();}
static BigDecimal bd(){ return sc.nextBigDecimal();}
static int [] IntArray(int n) {
int [] Array = new int[n];
for(int i=0;i<n;i++) Array[i] = ni();
return Array;
}
static int [][] IntArray(int n , int m) {
int [][] Array = new int[n][m];
for(int i=0;i<n;i++) for(int j=0;j<m;j++) Array[i][j] = ni();
return Array;
}
static long [] LongArray(int n) {
long [] Array = new long[n];
for(int i=0;i<n;i++) Array[i] = nl();
return Array;
}
static long [][] LongArray(int n , int m) {
long [][] Array = new long[n][m];
for(int i=0;i<n;i++) for(int j=0;j<m;j++) Array[i][j] = nl();
return Array;
}
static double [] DoubleArray(int n) {
double [] Array = new double[n];
for(int i=0;i<n;i++) Array[i] = nd();
return Array;
}
static double [][] DoubleArray(int n , int m) {
double [][] Array = new double[n][m];
for(int i=0;i<n;i++) for(int j=0;j<m;j++) Array[i][j] = nd();
return Array;
}
static String [] StringArray(int n) {
String [] Array = new String[n];
for(int i=0;i<n;i++) Array[i] = ns();
return Array;
}
static String [][] StringArray(int n , int m) {
String [][] Array = new String[n][m];
for(int i=0;i<n;i++) for(int j=0;j<m;j++) Array[i][j] = ns();
return Array;
}
static char [] CharArray(int n) {
char [] Array = new char[n];
String S = ns();
for(int i=0;i<n;i++) Array[i] = S.charAt(i);
return Array;
}
static char [][] CharArray(int n,int m) {
char [][] Array = new char[n][m];
for(int i=0;i<n;i++) {
String S = ns();
for(int j=0;j<m;j++) Array[i][j] = S.charAt(j);
}
return Array;
}
static void PrintArray(int [] A) {
for(int i=0;i<A.length;i++) output.print(A[i]+" ");
output.println();
}
static void PrintArray(long [] A) {
for(int i=0;i<A.length;i++) output.print(A[i]+" ");
output.println();
}
static void PrintArray(double [] A) {
for(int i=0;i<A.length;i++) output.print(A[i]+" ");
output.println();
}
static void PrintArray(boolean [] A) {
for(int i=0;i<A.length;i++) output.print(A[i]+" ");
output.println();
}
static void PrintArray(int [][] A) {
for(int i=0;i<A.length;i++) {
for(int j=0;j<A[i].length;j++) {
if(A[i][j] == Inf) output.print("X ");
else output.print(A[i][j]+" ");
}
output.println();
}
}
static void PrintArray(long [][] A) {
for(int i=0;i<A.length;i++) {
for(int j=0;j<A[i].length;j++) {
if(A[i][j] == Lnf) output.print("X ");
else output.print(A[i][j]+" ");
}
output.println();
}
}
static void PrintArray(boolean [][] A) {
for(int i=0;i<A.length;i++) {
for(int j=0;j<A[i].length;j++) {
output.print(A[i][j]?"O":"X");
}
output.println();
}
}
public static void main(String[] args){
output = new PrintWriter(System.out);
sc = new Scanner(System.in);
solve();
output.flush();
}
}