QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760628#4629. Longest Increasing Subsequencecjr2010WA 0ms3624kbC++14760b2024-11-18 18:01:132024-11-18 18:01:14

Judging History

你现在查看的是最新测评结果

  • [2024-11-18 18:01:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3624kb
  • [2024-11-18 18:01:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[100005],f[100005][65];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("lis.in","r",stdin);
//	freopen("lis.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<=61;i++) f[1][i]=1;
	for(int i=2;i<=n;i++)
	{
		ll x=a[i]-a[i-1],w=__lg(x);
		if(w==0) f[i][0]=f[i-1][0]+1;
		else
		{
			for(int j=0;j<w;j++)
			{
				f[i][j+1]=f[i-1][j+1]+(1ll<<j);
			}
			ll w1=x-(1ll<<w),w2=1ll<<(w-1);
			f[i][w]=max(f[i-1][w]+w1,f[i-1][w-1]+max(w1,w2)+(w1>0));
		}
		for(int j=0;j<=61;j++)
		{
			f[i][j]=max(f[i][j],f[i-1][j]);
			if(j) f[i][j]=max(f[i][j],f[i][j-1]);
		}
	}
	cout<<f[n][61];
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3624kb

input:

7
7 41 53 58 75 78 81

output:

18

result:

wrong answer 1st lines differ - expected: '22', found: '18'