QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#559213 | #4629. Longest Increasing Subsequence | World_Creater | WA | 0ms | 3608kb | C++17 | 630b | 2024-09-11 20:51:00 | 2024-09-11 20:51:00 |
Judging History
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'