Submission #1836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1836		alephnull	앱 (KOI13_app)	C++98	21 / 21	12 ms	8900 KiB

app

#include <cstdio> 
#include <cstring> 
#include <algorithm> 
#define INF 7654321 
using namespace std; 
int n,m; 
int a[100],c[100]; 
long long cache[100][10001]; 
int dp(int idx,int value){ 
    if(value<0)return -INF; 
    if(idx<0)return 0; 
    if(cache[idx][value]!=-1)return cache[idx][value]; 
    long long &ret=cache[idx][value]; 
    return ret=max(dp(idx-1,value),dp(idx-1,value-c[idx])+a[idx]); 
} 
int main(){ 
    scanf("%d %d",&n,&m); 
    for(int i=0;i<n;i++)scanf("%d",a+i); 
    for(int i=0;i<n;i++)scanf("%d",c+i); 
    memset(cache,-1,sizeof(cache)); 
    int sum=0; 
    for(int i=0;i<n;i++)sum+=c[i]; 
    for(int i=0;i<n;i++) 
        for(int j=0;j<sum;j++) 
            dp(i,j); 
    int ans=INF; 
    for(int i=0;i<n;i++) 
        for(int j=0;j<sum;j++) 
            if(cache[i][j]>=m) 
                if(ans>j)ans=j; 
    printf("%d",ans); 
} 

• Subtask 1: 3.15 / 3.15
• Subtask 2: 3.15 / 3.15
• Subtask 3: 3.15 / 3.15
• Subtask 4: 3.15 / 3.15
• Subtask 5: 3.15 / 3.15
• Subtask 6: 3.15 / 3.15
• Subtask 7: 2.1 / 2.1