Dima, Inna and Seryozha have gathered in a room. That's right, someone's got to go. To cheer Seryozha up and inspire him to have a walk, Inna decided to cook something.
Dima and Seryozha havenfruits in the fridge. Each fruit has two parameters: the taste and the number of calories. Inna decided to make a fruit salad, so
she wants to take some fruits from the fridge for it. Inna follows a certain principle as she chooses the fruits: the total taste to the total calories ratio of the chosen fruits must equalk.
In other words,,
whereajis
the taste of thej-th chosen fruit andbjis
its calories.
Inna hasn't chosen the fruits yet, she is thinking: what is the maximum taste of the chosen fruits if she strictly follows her principle? Help Inna solve this culinary problem — now the happiness of a young couple is in your hands!
Inna loves Dima very much so she wants to make the salad from at least one fruit.
Output
If there is no way Inna can choose the fruits for the salad, print in the single line number -1. Otherwise, print a single integer — the maximum possible sum of the taste values of the chosen fruits.
Note
In the first test sample we can get the total taste of the fruits equal to 18 if we choose fruit number 1 and fruit number 2, then the total calories will equal 9. The conditionfulfills,
that's exactly what Inna wants.
In the second test sample we cannot choose the fruits so as to follow Inna's principle.
需要把tastes , calories变形成 tastes-k*calories 这样两个变量就统一起来了。。。然后问题变成n个数相加为0的权值最大,简单DP。。。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct node
{
int a,b,c;
}w[110];
int n,k,dp[25000];
const int base=11000;
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&w[i].a);
for(int i=0;i<n;i++) scanf("%d",&w[i].b),w[i].c=w[i].a-k*w[i].b;
memset(dp,-1,sizeof(dp));
dp[base]=0;
for(int j=0;j<n;j++)
{
int d=w[j].c>=0?-1:1;
for(int i=-10000*d;i!=10000*d;i+=d)
{
if(dp[i+base]>=0)
{
int t=i+w[j].c;
if(t>=-10000&&t<=10000)
{
dp[t+base]=max(dp[t+base],dp[i+base]+w[j].a);
}
}
}
}
if(dp[base]==0) printf("-1\n");
else printf("%d\n",dp[base]);
return 0;
}
分享到:
相关推荐
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
Codeforces round 678 D2_Codeforces_源码
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
打codeforces的神器
codeforces-js Codeforces JS
PDF-CodeForces问题 PDF文件中的CodeForces问题 利用CodeForces提取在这个库中的文件 ,文件夹名代表来自CodeForces网址contests`的ID,每个文件夹包含比赛的问题。 有关CodeForces竞赛的疯狂事实 CodeForces上有937...
# sublime-plugin-for-codeforces 自定义构建,用于从 codeforces 获取测试用例并检查程序是否正确。 平台:GNU/Linux 语言:Python2.7.9 描述:这个程序从 codeforces 中获取测试用例,并告诉你程序的输出是否与...
Codeforces Round #723 (Div. 2).md
使用 C# + WPF 开发 --- 还在发愁打了那么多场比赛都没有进入首页么? 还在为了前 5 的 hacker 名额阅读千份代码么? 是的,你没有看错! 这是一个 Edu & Div.3 轮 Open hacking 错误代码自动查找器!...