zech的神秘题库(武汉理工夜莺杯)
乍一看，应该是个背包不错了，一看数据，扯犊子呢，数组开不到那么大
这个题的关键就是
（1）物品是连续的，即1,2,3,4,5，，，，n
（2）每件物品至少有一件
先判断为-1的情况：
所有物品总量和还要小于m，这样再怎么也拼不够
再考虑物品总量>=m
这样总能找到一组，使之和为m！！！！！
为什么？
假设总量为sum,(从前往后依次选择，没次都把难度为i的题目选择完，直到超过m)
设此时最高难度为x，
m-sum
因为性质（1）（2），所以我们总能在[1,x-1]找到一个难度==m-sum,不选择它
这个题有点妙啊
#include
using namespace std;
#define int long long
long long read(){
long long ret=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int n,m;
int a[10011];
signed main(){
n = read();m = read();
int sum = 0;
for(int i = 1; i <= n; i++){
a[i] = read();
sum += a[i] * i;
}
if(sum < m){
puts("-1");
return 0;
}
int ans = 0;
for(int i = 1; i <= n; i++){
if(m > a[i] * i){
ans += a[i];
m -= a[i] * i;
}else{
while(m >= i){
m -= i;
ans ++;
}
break;
}
}
cout << ans << endl;
return 0;
}