Codeforces 331A2 - Oh Sweet Beaverette (70 points)

貪心搞就行，用map記錄每個數出現的下標，每次都取首尾兩個。將中間權值為負的刪掉後取sum值最大的就行。

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define LL long long

using namespace std;

const int maxn = 333333;
int n, a[maxn], l, r, k, ans[maxn];
LL s[maxn];
map<int, vector<int> > mp;
map<int, vector<int> > :: 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;
}