QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620611#4629. Longest Increasing Subsequenceship2077WA 0ms3712kbC++23922b2024-10-07 19:46:482024-10-07 19:46:50

Judging History

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

  • [2024-10-07 19:46:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3712kb
  • [2024-10-07 19:46:48]
  • 提交

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'