C++14(g++5.4) 解法, 执行用时: 72ms, 内存消耗: 1996K, 提交时间: 2020-05-30 16:03:40

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
typedef long long ll;

int a[maxn],dp[maxn],pos[maxn],seq[maxn];
int main(){
	int n,P;
	scanf("%d%d",&n,&P);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}

	int len=0;
	for(int i=1;i<=n;i++){
		if(len==0||a[i]>dp[len]){
			dp[++len]=a[i];
			pos[i]=len;
		}
		else{
			*(lower_bound(dp+1,dp+1+len,a[i])) = a[i];
			pos[i] = lower_bound(dp+1,dp+1+len,a[i]) - dp;
		}
	}
	int t=len,m=len;
	ll ans=P;
	for(int i=n;i>=1;i--){
		if(pos[i]==t){
			seq[t--]=i;
			ans += a[i];
		}
		if(!t) break;
	}
	printf("%lld\n%d\n",ans,m);
	for(int i=1;i<=m;i++) printf("%d\n",seq[i]);
    return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 234ms, 内存消耗: 40360K, 提交时间: 2020-05-24 16:57:34

n,P=map(int,input().split(' '))
a=list(map(int,input().split(' ')))

f=[0]*(n+1)
b=[-1]*(n+1)
r=1

for i in range(1,n):
    if a[i]<a[f[0]]:
        f[0]=i
    elif a[i]>a[f[r-1]]:
        b[i]=f[r-1]
        f[r]=i
        r+=1
    else:
        L=-1
        R=r-1
        while L+1<R:
            m=(L+R)//2
            if a[f[m]]>=a[i]:R=m
            else:L=m
        b[i]=f[R-1]
        f[R]=i

al=[]
p=f[r-1]
s=0
while p>=0:
    al.append(p)
    s+=a[p]
    p=b[p]

print(P+s)
print(len(al))
for p in reversed(al):
    print(p+1)

C++11(clang++ 3.9) 解法, 执行用时: 45ms, 内存消耗: 3808K, 提交时间: 2020-06-28 12:53:37

#include<bits/stdc++.h>
using namespace std;

int t=0,a[200005],S[200005],V[200005],T[200005];
int main()
{
	int i,j,n;
	long long ans;
	scanf("%d%lld",&n,&ans);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(!t)S[++t]=a[i],V[i]=t;
		else
		{
			if(a[i]>S[t])S[++t]=a[i],V[i]=t;
			else j=lower_bound(S+1,S+1+t,a[i])-S,S[j]=a[i],V[i]=j;
		}
	}
	for(j=t,i=n;j&&i>=1;i--)if(V[i]==j)ans+=a[i],T[j--]=i;
	printf("%lld\n%d\n",ans,t);
	for(i=1;i<=t;i++)printf("%d\n",T[i]);
}