Submission #2940999
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; class Main{ static class Node{ int v,w; Node(int v,int w){this.v=v;this.w=w;} } static void solve(){ int n = ni(); int p= ni(); PriorityQueue<Node> que = new PriorityQueue<>((a,b)->b.w-a.w); for(int i=0;i<n;++i){ int a = ni(), b=ni(); que.add(new Node(b,a)); } int[][] dp = new int[n+1][p+101]; int ans = 0; for(int i=0;i<n;++i){ Node node = que.poll(); for(int j=0;j<=p+node.w;++j){ dp[i+1][j]=dp[i][j]; if(j-node.w>=0)dp[i+1][j] = Math.max(dp[i][j], dp[i][j-node.w]+node.v); } ans = Math.max(ans, dp[i+1][p+node.w]); } out.println(ans); } public static void main(String[] args){ solve(); out.flush(); } private static InputStream in = System.in; private static PrintWriter out = new PrintWriter(System.out); private static final byte[] buffer = new byte[1<<15]; private static int ptr = 0; private static int buflen = 0; private static boolean hasNextByte(){ if(ptr<buflen)return true; ptr = 0; try{ buflen = in.read(buffer); } catch (IOException e){ e.printStackTrace(); } return buflen>0; } private static int readByte(){ if(hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isSpaceChar(int c){ return !(33<=c && c<=126);} private static int skip(){int res; while((res=readByte())!=-1 && isSpaceChar(res)); return res;} private static double nd(){ return Double.parseDouble(ns()); } private static char nc(){ return (char)skip(); } private static String ns(){ StringBuilder sb = new StringBuilder(); for(int b=skip();!isSpaceChar(b);b=readByte())sb.append((char)b); return sb.toString(); } private static int[] nia(int n){ int[] res = new int[n]; for(int i=0;i<n;++i)res[i]=ni(); return res; } private static long[] nla(int n){ long[] res = new long[n]; for(int i=0;i<n;++i)res[i]=nl(); return res; } private static int ni(){ int res=0,b; boolean minus=false; while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); if(b=='-'){ minus=true; b=readByte(); } for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); return minus ? -res:res; } private static long nl(){ long res=0,b; boolean minus=false; while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); if(b=='-'){ minus=true; b=readByte(); } for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); return minus ? -res:res; } }
Submission Info
Submission Time | |
---|---|
Task | C - おやつ |
User | inmir |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 2781 Byte |
Status | AC |
Exec Time | 356 ms |
Memory | 168996 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 | sample_01.txt, sample_02.txt, subtask1_00.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt |
Subtask2 | sample_01.txt, sample_02.txt, sample_03.txt, subtask1_00.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask2_00.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 182 ms | 25040 KB |
sample_02.txt | AC | 151 ms | 24660 KB |
sample_03.txt | AC | 153 ms | 23636 KB |
subtask1_00.txt | AC | 158 ms | 26452 KB |
subtask1_01.txt | AC | 153 ms | 24404 KB |
subtask1_02.txt | AC | 142 ms | 25044 KB |
subtask1_03.txt | AC | 142 ms | 26068 KB |
subtask1_04.txt | AC | 145 ms | 24404 KB |
subtask1_05.txt | AC | 153 ms | 26708 KB |
subtask1_06.txt | AC | 144 ms | 25172 KB |
subtask1_07.txt | AC | 154 ms | 24276 KB |
subtask1_08.txt | AC | 161 ms | 25684 KB |
subtask1_09.txt | AC | 147 ms | 24020 KB |
subtask1_10.txt | AC | 153 ms | 26580 KB |
subtask1_11.txt | AC | 153 ms | 22100 KB |
subtask1_12.txt | AC | 147 ms | 26452 KB |
subtask1_13.txt | AC | 154 ms | 25684 KB |
subtask1_14.txt | AC | 147 ms | 24020 KB |
subtask2_00.txt | AC | 178 ms | 31828 KB |
subtask2_01.txt | AC | 193 ms | 52948 KB |
subtask2_02.txt | AC | 283 ms | 130640 KB |
subtask2_03.txt | AC | 182 ms | 34644 KB |
subtask2_04.txt | AC | 204 ms | 53972 KB |
subtask2_05.txt | AC | 262 ms | 93140 KB |
subtask2_06.txt | AC | 169 ms | 23892 KB |
subtask2_07.txt | AC | 174 ms | 33868 KB |
subtask2_08.txt | AC | 171 ms | 26324 KB |
subtask2_09.txt | AC | 192 ms | 54356 KB |
subtask2_10.txt | AC | 335 ms | 165040 KB |
subtask2_11.txt | AC | 347 ms | 163520 KB |
subtask2_12.txt | AC | 346 ms | 167748 KB |
subtask2_13.txt | AC | 341 ms | 163376 KB |
subtask2_14.txt | AC | 356 ms | 161076 KB |
subtask2_15.txt | AC | 341 ms | 163648 KB |
subtask2_16.txt | AC | 348 ms | 164380 KB |
subtask2_17.txt | AC | 331 ms | 163260 KB |
subtask2_18.txt | AC | 351 ms | 168996 KB |
subtask2_19.txt | AC | 341 ms | 162868 KB |