UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214994#2481. 或yiwei201221ms118640kbC++111.7kb2024-11-25 19:28:542024-11-25 23:04:05

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 5005, NN = 2e5 + 5;

int n,K,x,a[N],g[N][N];

int f[N][20];

int pre[NN], suf[NN];

int b[NN];

signed main(){
    cin >> n >> K >> x;
    if (n > 5000){
        for (int i = 1;i <= n;i++)
            cin >> b[i];
        if (K == 1){
            for (int i = 1;i <= n;i++)
                pre[i] = pre[i - 1] | b[i];
            for (int i = n;i >= 1;i--)
                suf[i] = suf[i + 1] | b[i];
            int ans = 0;
            for (int i = 1;i <= n;i++){
                ans = max(ans,pre[i - 1] | suf[i + 1] | (b[i] * x));
            }
            cout << ans;
        }
        else{
            sort(b + 1,b + n + 1,[](int x,int y){
                return y > x;
            });
            for (int i = 1;i <= K;i++){
                b[i] *= x;
            }
            int ans = 0;
            for (int i = 1;i <= n;i++)
                ans |= b[i];
            cout << ans;
        }
        return 0;
    }
    for (int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for (int i = 1;i <= n;i++){
        g[i][i] = a[i];
        for (int j = i + 1;j <= n;j++){
            g[i][j] = g[i][j - 1] | a[j];
        }
    }
    for (int i = 1;i <= n;i++){
        for (int j = 0;j < i;j++){
            for (int k = 0;k <= min(K,i);k++){
                if (k)
                    f[i][k] = max(f[i][k],f[j][k - 1] | g[j + 1][i - 1] | (a[i] * x));
                f[i][k] = max(f[i][k],f[j][k] | g[j + 1][i]);
            }
        }
    }
    int ans = 0;
    for (int i = 1;i <= K;i++)
        ans = max(ans,f[n][i]);
    cout << ans;
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 1228kb

input:

5 1 7
0 8 1048584 1572872 524296

output:

12058680

result:

ok single line: '12058680'

Test #2:

score: 0
Accepted
time: 0ms
memory: 1232kb

input:

5 1 4
266252 262153 266249 9 262144

output:

1331257

result:

ok single line: '1331257'

Test #3:

score: 0
Accepted
time: 0ms
memory: 1228kb

input:

5 1 3
262280 8388620 42205192 33554440 41943052

output:

126615708

result:

ok single line: '126615708'

Test #4:

score: 0
Accepted
time: 0ms
memory: 1228kb

input:

5 1 5
72353802 340805641 273680394 271583243 69748747

output:

1979279407

result:

ok single line: '1979279407'

Test #5:

score: 0
Accepted
time: 2ms
memory: 1228kb

input:

5 1 6
84165274 556269848 84673192 69222560 69484808

output:

3355199418

result:

ok single line: '3355199418'

Test #6:

score: 0
Accepted
time: 0ms
memory: 1228kb

input:

5 1 3
606143041 607191138 536870912 77628003 612466691

output:

1840611947

result:

ok single line: '1840611947'

Test #7:

score: 0
Accepted
time: 0ms
memory: 1232kb

input:

5 1 8
268468225 33557000 809500676 268470532 268438284

output:

6744476461

result:

ok single line: '6744476461'

Test #8:

score: 0
Accepted
time: 0ms
memory: 1228kb

input:

5 1 3
6817368 541738269 805322758 537542681 806093397

output:

2960050015

result:

ok single line: '2960050015'

Test #9:

score: 0
Accepted
time: 0ms
memory: 1232kb

input:

5 1 4
92293679 75499622 830777890 362031721 17072134

output:

3616991983

result:

ok single line: '3616991983'

Test #10:

score: 0
Accepted
time: 0ms
memory: 1228kb

input:

5 1 6
847251150 37750148 813697674 306187520 830479940

output:

5364531166

result:

ok single line: '5364531166'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 0ms
memory: 1228kb

input:

5 3 4
4194308 0 4 0 4194304

output:

20971540

result:

wrong answer 1st lines differ - expected: '272630020', found: '20971540'

Subtask #3:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 0ms
memory: 1248kb

input:

10 5 3
0 0 32776 8 33587200 33587200 33554432 32768 33554432 32768

output:

100761624

result:

wrong answer 1st lines differ - expected: '8161689608', found: '100761624'

Subtask #4:

score: 0
Wrong Answer

Test #31:

score: 0
Wrong Answer
time: 0ms
memory: 1288kb

input:

20 2 7
4 0 16777216 16777220 4 16777220 4 16777216 0 4 16777216 16777220 16777220 4 0 16777220 16777...

output:

117440540

result:

wrong answer 1st lines differ - expected: '822083780', found: '117440540'

Subtask #5:

score: 0
Wrong Answer

Test #41:

score: 0
Wrong Answer
time: 0ms
memory: 1292kb

input:

20 10 5
262144 263168 262144 262144 1024 268435456 262144 1024 262144 262144 262144 0 262144 2686986...

output:

1343493120

result:

wrong answer 1st lines differ - expected: '2624010268435456', found: '1343493120'

Subtask #6:

score: 0
Wrong Answer

Test #51:

score: 0
Wrong Answer
time: 0ms
memory: 4260kb

input:

500 3 6
536879104 536879104 536879104 8 8200 8192 536879104 8 536870920 8192 536879112 536879104 536...

output:

3758153784

result:

wrong answer 1st lines differ - expected: '116502767304', found: '3758153784'

Subtask #7:

score: 0
Wrong Answer

Test #61:

score: 0
Wrong Answer
time: 387ms
memory: 118640kb

input:

5000 4 6
268435456 0 64 268435520 268435520 66 268435458 268435520 66 2 64 268435456 268435456 64 64...

output:

1879048654

result:

wrong answer 1st lines differ - expected: '348160872034', found: '1879048654'

Subtask #8:

score: 10
Accepted

Test #71:

score: 10
Accepted
time: 52ms
memory: 5888kb

input:

200000 1 2
136 524288 524296 524416 136 128 524288 128 136 0 136 136 136 0 128 0 524424 0 524416 524...

output:

1573272

result:

ok single line: '1573272'

Test #72:

score: 0
Accepted
time: 74ms
memory: 5892kb

input:

200000 1 3
67108865 16777217 21037056 65537 20971521 1 16842753 16842753 67108865 83951617 65536 209...

output:

264437763

result:

ok single line: '264437763'

Test #73:

score: 0
Accepted
time: 76ms
memory: 5888kb

input:

200000 1 3
134418440 402788392 402718760 196664 135216 134217752 40 402853912 134807608 725000 40285...

output:

1479225528

result:

ok single line: '1479225528'

Test #74:

score: 0
Accepted
time: 74ms
memory: 5888kb

input:

200000 1 2
536871951 33794 537001993 671252488 537001990 131080 134217738 132103 134251523 671089675...

output:

2013760543

result:

ok single line: '2013760543'

Test #75:

score: 0
Accepted
time: 64ms
memory: 5888kb

input:

200000 1 3
796800 2762752 2100640 2229408 158880 2384896 2508960 2884640 3032480 2124192 2386304 402...

output:

11501536

result:

ok single line: '11501536'

Test #76:

score: 0
Accepted
time: 77ms
memory: 5888kb

input:

200000 1 2
940310800 805315088 139207268 805306416 939786292 675807568 134750244 138674964 809771636...

output:

2027710460

result:

ok single line: '2027710460'

Test #77:

score: 0
Accepted
time: 75ms
memory: 5892kb

input:

200000 1 2
538002688 22016 271872 538001984 2115392 572600384 571487552 36964096 16384 572588864 540...

output:

1719664576

result:

ok single line: '1719664576'

Test #78:

score: 0
Accepted
time: 83ms
memory: 5888kb

input:

200000 1 2
878103600 939967672 618053656 2411824 811994168 939689072 550817248 548456904 149340288 8...

output:

2113921016

result:

ok single line: '2113921016'

Test #79:

score: 0
Accepted
time: 54ms
memory: 5888kb

input:

200000 1 5
718277636 540311600 947126292 849710084 584420392 820347908 854656016 570426372 14943272 ...

output:

5368692028

result:

ok single line: '5368692028'

Test #80:

score: 0
Accepted
time: 76ms
memory: 5892kb

input:

200000 1 5
845562150 71840768 811598720 342492322 644228646 70140706 604387204 839398404 541746722 1...

output:

5368709054

result:

ok single line: '5368709054'

Subtask #9:

score: 0
Wrong Answer

Test #81:

score: 0
Wrong Answer
time: 73ms
memory: 2764kb

input:

200000 6 7
67108864 536870912 71303168 67108864 608174080 541065216 67108864 608174080 536870912 536...

output:

608174080

result:

wrong answer 1st lines differ - expected: '71551676317696', found: '608174080'

Subtask #10:

score: 0
Wrong Answer

Test #91:

score: 0
Wrong Answer
time: 54ms
memory: 2760kb

input:

200000 7 2
4 67108864 4 67108868 1 1 67108869 0 67108869 67108868 67108864 1 67108864 67108868 67108...

output:

67108869

result:

wrong answer 1st lines differ - expected: '8657044101', found: '67108869'