两道水

2793: [Poi2012]Vouchers：暴力加小优化，据说是O(mlogm)的。

2091: [Poi2010]The Minima Game：之前做的USACO10的taking turns。。。一样的题额。。

#include<cstdio>
#include<cstring>
typedef long long ll;
int m,n;
ll x,maxi=0,tot=0,sum=0;
ll d[1000001];
ll ans[1000001];
bool c[1000001],f[1000001];
ll max(ll a,ll b){return a>b? a:b;}
int main(){
    scanf("%d",&m);
    memset(f,true,sizeof(f));
    for (int i=1;i<=m;i++){
        scanf("%lld",&x);
        c[x]=true;
        maxi=max(maxi,x);
    }
    scanf("%d",&n);
    for (int i=1;i<=maxi;i++){
        d[i]=i;
    }
    for (int i=1;i<=n;i++){
        scanf("%lld",&x);
        int s=x;
        long long y=d[x];
        while (s){
            if (y>maxi) break;
            if (f[y]){
                tot++;
                d[x]=y;
                f[y]=false;
                //printf("y=%d\n",y);
                if (c[y]) ans[++sum]=tot;
                s--;
            }
            y+=x;
        }
        //printf("s=%d tot=%d\n",s,tot);
        tot+=s;
    }
    printf("%lld\n",sum);
    for (int i=1;i<=sum;i++){
        printf("%lld\n",ans[i]);
    }
}

#include<cstdio>
#include<algorithm>
int n;
long long a[1000001],f[1000001];
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    std::sort(a+1,a+n+1);
    for (int i=1;i<=n;i++){
        f[i]=std::max(f[i-1],a[i]-f[i-1]);
    }
    printf("%lld\n",f[n]);
}