zech的神秘题库(武汉理工夜莺杯)

乍一看，应该是个背包不错了，一看数据，扯犊子呢，数组开不到那么大
这个题的关键就是
（1）物品是连续的，即1,2,3,4,5，，，，n
（2）每件物品至少有一件
先判断为-1的情况：
所有物品总量和还要小于m，这样再怎么也拼不够
再考虑物品总量>=m
这样总能找到一组，使之和为m！！！！！
为什么？
假设总量为sum,(从前往后依次选择，没次都把难度为i的题目选择完，直到超过m)
设此时最高难度为x，
m-sum<x
因为性质（1）（2），所以我们总能在[1,x-1]找到一个难度==m-sum,不选择它
这个题有点妙啊

	#include<bits/stdc++.h>
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;
}