oj.uz

Submission #1100

# Submission time Handle Problem Language Result Execution time Memory
1100 2013-06-25T06:37:23 Z leecs0503 앱 (KOI13_app) C++
21 / 21
 872 ms 79212 KB 
#include<stdio.h>

//FILE *input=freopen("input.txt","r",stdin);

#define MAX 20000001

int dp[MAX];
int a[101];
int b[101];

int main(){
	int n,m,i,j,maxi=0,r,mini;
	scanf("%d%d",&n,&m);

	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		if(maxi<a[i])
			maxi=a[i];
	}
	for(i=0;i<n;i++){
		scanf("%d",&b[i]);
	}

	for(i=0;i<=m+maxi;i++){
		dp[i]=-1;
	}
	dp[0]=0;
	for(i=0;i<n;i++){
		for(j=m-1;j>=0;j--){
			if(dp[j]==-1)
				continue;
			r=dp[j]+b[i];
			if(dp[j+a[i]]>r||dp[j+a[i]]==-1){
				dp[j+a[i]]=r;
			}
		}
	}
	mini=100001;
	for(j=m;j<m+maxi;j++){
		if(dp[j]<mini&&dp[j]!=-1){
			mini=dp[j];
		}
	}
	printf("%d",mini);

	return 0;
}

Subtask #1
3.15 / 3.15

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

Subtask #2
3.15 / 3.15

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

Subtask #3
3.15 / 3.15

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

Subtask #4
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 79212 KB Output is correct
2 Correct 40 ms 79212 KB Output is correct
3 Correct 20 ms 79212 KB Output is correct
4 Correct 52 ms 79212 KB Output is correct
5 Correct 32 ms 79212 KB Output is correct
6 Correct 0 ms 79212 KB Output is correct

Subtask #5
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 540 ms 79212 KB Output is correct
2 Correct 708 ms 79212 KB Output is correct
3 Correct 872 ms 79212 KB Output is correct
4 Correct 592 ms 79212 KB Output is correct
5 Correct 148 ms 79212 KB Output is correct
6 Correct 52 ms 79212 KB Output is correct

Subtask #6
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 780 ms 79212 KB Output is correct
2 Correct 200 ms 79212 KB Output is correct
3 Correct 4 ms 79212 KB Output is correct
4 Correct 596 ms 79212 KB Output is correct
5 Correct 48 ms 79212 KB Output is correct
6 Correct 636 ms 79212 KB Output is correct

Subtask #7
2.1 / 2.1

# Verdict Execution time Memory Grader output
1 Correct 248 ms 79212 KB Output is correct
2 Correct 500 ms 79212 KB Output is correct
3 Correct 864 ms 79212 KB Output is correct
4 Correct 652 ms 79212 KB Output is correct