oj.uz

Submission #1836

# Submission time Handle Problem Language Result Execution time Memory
1836 2013-07-18T03:37:47 Z alephnull 앱 (KOI13_app) C++
21 / 21
 12 ms 8900 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8900 KB Output is correct
2 Correct 0 ms 8900 KB Output is correct
3 Correct 0 ms 8900 KB Output is correct
4 Correct 0 ms 8900 KB Output is correct
5 Correct 4 ms 8900 KB Output is correct
6 Correct 0 ms 8900 KB Output is correct

Subtask #2
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8900 KB Output is correct
2 Correct 0 ms 8900 KB Output is correct
3 Correct 4 ms 8900 KB Output is correct
4 Correct 0 ms 8900 KB Output is correct
5 Correct 0 ms 8900 KB Output is correct

Subtask #3
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8900 KB Output is correct
2 Correct 0 ms 8900 KB Output is correct
3 Correct 4 ms 8900 KB Output is correct
4 Correct 0 ms 8900 KB Output is correct
5 Correct 0 ms 8900 KB Output is correct
6 Correct 0 ms 8900 KB Output is correct

Subtask #4
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8900 KB Output is correct
2 Correct 0 ms 8900 KB Output is correct
3 Correct 4 ms 8900 KB Output is correct
4 Correct 0 ms 8900 KB Output is correct
5 Correct 0 ms 8900 KB Output is correct
6 Correct 0 ms 8900 KB Output is correct

Subtask #5
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8900 KB Output is correct
2 Correct 4 ms 8900 KB Output is correct
3 Correct 12 ms 8900 KB Output is correct
4 Correct 8 ms 8900 KB Output is correct
5 Correct 4 ms 8900 KB Output is correct
6 Correct 0 ms 8900 KB Output is correct

Subtask #6
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8900 KB Output is correct
2 Correct 4 ms 8900 KB Output is correct
3 Correct 4 ms 8900 KB Output is correct
4 Correct 4 ms 8900 KB Output is correct
5 Correct 8 ms 8900 KB Output is correct
6 Correct 8 ms 8900 KB Output is correct

Subtask #7
2.1 / 2.1

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8900 KB Output is correct
2 Correct 8 ms 8900 KB Output is correct
3 Correct 8 ms 8900 KB Output is correct
4 Correct 8 ms 8900 KB Output is correct