QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#760628 | #4629. Longest Increasing Subsequence | cjr2010 | WA | 0ms | 3624kb | C++14 | 760b | 2024-11-18 18:01:13 | 2024-11-18 18:01:14 |
Judging History
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'