QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#559213#4629. Longest Increasing SubsequenceWorld_CreaterWA 0ms3608kbC++17630b2024-09-11 20:51:002024-09-11 20:51:00

Judging History

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

  • [2024-09-11 20:51:00]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3608kb
  • [2024-09-11 20:51:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[100005],f[100005][65];
int main()
{
	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++)
	{
		int 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]=f[i-1][j]+(1ll<<j);
			}
			int w1=x-(1ll<<w),w2=1ll<<(w-1);
			f[i][w]=max(f[i-1][w]+w1,f[i-1][w-1]+max(w1+(w1>0),w2));
		}
		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: 3608kb

input:

7
7 41 53 58 75 78 81

output:

21

result:

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