Codeforces 331A2 - Oh Sweet Beaverette (70 points) - c++编程基础

贪心搞就行，用map记录每个数出现的下标，每次都取首尾两个。将中间权值为负的删掉后取sum值最大的就行。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FF(i, a, b) for(int i=a; ib; i--)
#define REP(i, n) for(int i=0; i > mp;
map > :: iterator it;

int main()
{
    while(~scanf("%d", &n))
    {
        s[0] = 0; mp.clear();
        LL sum = -111111111111, tmp;
        FF(i, 1, 1+n)
        {
            scanf("%d", &a[i]);
            if(a[i] >




 0) s[i] = s[i-1] + a[i];
            else s[i] = s[i-1];
            mp[a[i]].push_back(i);
        }
        for(it = mp.begin(); it != mp.end(); it++)
        {
            int nc = it->second.size();
            if(nc >= 2)
            {
                tmp = s[it->second[nc-1]] - s[it->second[0]-1];
                if(it->first < 0) tmp += it->first*2;
                if(tmp > sum)
                {
                    sum = tmp, l = it->second[0], r = it->second[nc-1];
                }
            }
        }
        k = 0;
        FF(i, 1, l) ans[k++] = i;
        FF(i, l+1, r) if(a[i] < 0) ans[k++] = i;
        FF(i, r+1, n+1) ans[k++] = i;
        printf("%I64d %d\n", sum, k);
        REP(i, k) printf("%d ", ans[i]);
    }
    return 0;
}