CF331A1&CF331A2-526互联

不难发现一件事：对于在 \(i\) 之后能跟 \(i\) 匹配的 \(j\)，最好的办法显然是使得 \(j\) 最大。则用前缀和统计整个和，并且用前缀和维护负数和，在枚举 \(i\) 统计出最小答案时在后面计算出满足最大答案的条件并输出即可。

ac records

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=3e5+10;
map<int,int>p;
int n,num,now_ans=LONG_LONG_MIN;
int a[maxn],b[maxn],c[maxn];
vector<int>ans;
void out_puts(int u){
    printf("%lld %lld\n",u,ans.size());
    for(int i=0;i<ans.size();++i)printf("%lld ",ans[i]);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){scanf("%lld",&a[i]);b[i]=b[i-1]+a[i];p[a[i]]=max(p[a[i]],i);if(a[i]<0)c[i]=c[i-1]+a[i];else c[i]=c[i-1];}
    for(int i=1;i<=n;++i){if(p[a[i]]==i)continue;now_ans=max(now_ans,b[p[a[i]]]-b[i-1]-(c[p[a[i]]-1]-c[i]));}
    for(int i=1;i<=n;++i){if(p[a[i]]==i)continue;if(now_ans==b[p[a[i]]]-b[i-1]-(c[p[a[i]]-1]-c[i])){num=0;for(int j=1;j<=n;++j){if(j<i || j>p[a[i]] || (a[j]<0 && j!=i && j!=p[a[i]])){ans.push_back(j);num+=a[j];}}out_puts(b[n]-num);return 0;}}
    return 0;
}

331