QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#620611 | #4629. Longest Increasing Subsequence | ship2077 | WA | 0ms | 3712kb | C++23 | 922b | 2024-10-07 19:46:48 | 2024-10-07 19:46:50 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int M=1e5+5;
int n,a[M],dp[M][62];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
signed main(){ n=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=0;i<=60;i++) dp[1][i]=1;
for (int i=2;i<=n;i++){
int delta=a[i]-a[i-1];
int len=63^__builtin_clzll(delta);
for (int j=0;j<len;j++)
dp[i][j]=dp[i-1][j]+(1ll<<j);
dp[i][len]=dp[i][len]+delta-(1ll<<len);
if ((1ll<<len)!=delta)
dp[i][len]=max(dp[i][len],dp[i-1][len-1]+delta-(1ll<<len)+1);
for (int j=0;j<=60;j++){
dp[i][j]=max(dp[i][j],dp[i-1][j]);
if (j) dp[i][j]=max(dp[i][j],dp[i][j-1]);
}
}
printf("%lld\n",dp[n][60]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3712kb
input:
7 7 41 53 58 75 78 81
output:
18
result:
wrong answer 1st lines differ - expected: '22', found: '18'