QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #769876 | #7566. Interval Addition | grass8cow | AC ✓ | 2122ms | 200572kb | C++17 | 507b | 2024-11-21 19:42:40 | 2024-11-21 19:42:40 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,dp[1<<24],m;
ll sum[1<<24],a[30],b[30];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=n;i;i--)a[i]-=a[i-1];n++;
for(int i=0;i<n;i++)if(a[i])b[m]=a[i],m++;
for(int s=0;s<(1<<m);s++)for(int i=0;i<m;i++)if((s>>i)&1)
sum[s]+=b[i];
for(int s=1;s<(1<<m);s++){
for(int t=0;t<m;t++)if((s>>t)&1)
dp[s]=max(dp[s],dp[s^(1<<t)]+(sum[s]==0));
}
return printf("%d",m-dp[(1<<m)-1]),0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3720kb
input:
5 1 2 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
6 1 1 4 5 1 4
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 2118ms
memory: 200516kb
input:
23 154867764 88416234 958556716 525347353 297126571 748390457 991684429 346718178 898503520 361211695 769645122 37543644 545129269 108357111 477091071 990326512 89442247 500865905 865261751 881423606 884862773 342044622 545846884
output:
23
result:
ok 1 number(s): "23"
Test #4:
score: 0
Accepted
time: 2122ms
memory: 200568kb
input:
23 120512728 488581138 644845116 520600533 100830035 819227263 160270658 973159498 726973004 621205731 645066544 284705591 139812862 771961411 928673722 774153929 872014266 753699081 71306808 6052789 859500856 467237467 917534614
output:
23
result:
ok 1 number(s): "23"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
10 625630902 579967568 160371090 238722458 707634839 237285041 459491010 454916131 608704408 709619323
output:
10
result:
ok 1 number(s): "10"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
1 46422493
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
23 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 499999953 499999953 499999953 499999953 499999953 499999953 499999953 499999953 500000000 500000000 500000000 500000000 500000000 500000000 500000000
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
23 500000011 500000011 500000026 500000026 500000026 500000026 500000026 500000026 500000026 500000045 500000045 500000015 500000015 500000015 500000015 500000000 500000096 500000041 500000041 500000041 500000096 500000096 500000000
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 4ms
memory: 4296kb
input:
23 500000000 500000000 500000066 500000073 500000073 500000182 500000182 500000087 500000169 500000169 500000133 500000133 500000035 500000035 499999871 499999865 499999865 499999865 500000154 500000072 500000072 500000096 500000000
output:
11
result:
ok 1 number(s): "11"
Test #10:
score: 0
Accepted
time: 2099ms
memory: 200512kb
input:
23 499999858 499999791 499999811 499999854 499999847 499999769 499999893 499999791 499999757 499999924 500000215 500000063 499999986 500000146 499999907 500000007 499999789 499999985 499999874 499999884 500000008 499999922 499999917
output:
19
result:
ok 1 number(s): "19"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
23 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500006627 500006627 500006627 500006627 500006627 500006627 500006627 500006627 500000000 500000000
output:
2
result:
ok 1 number(s): "2"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
23 500000000 499991668 499991668 499991668 499991668 499991668 499992421 499992421 499992421 499992421 499992421 499992421 499992421 499991701 499991701 500007356 500007323 500007323 500007323 500007323 500007323 500007323 500006700
output:
6
result:
ok 1 number(s): "6"
Test #13:
score: 0
Accepted
time: 4ms
memory: 4148kb
input:
23 500008971 500007158 500007158 500007158 500007158 500007158 500016740 500016740 500023431 500029646 500031770 500025555 500025555 500025555 500025555 500020962 500011380 500014021 500011069 500012381 500009692 500005314 500005314
output:
11
result:
ok 1 number(s): "11"
Test #14:
score: 0
Accepted
time: 2088ms
memory: 200516kb
input:
23 500004790 500011043 500001539 499988427 499989318 500002907 499992442 500000344 500013204 500032360 500022060 500005386 499989135 499995181 499970440 499974934 499970234 499985465 499988500 499997841 499978295 499995992 499985112
output:
21
result:
ok 1 number(s): "21"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
23 500000000 500000000 500775103 500775103 500775103 500775103 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000
output:
2
result:
ok 1 number(s): "2"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
23 500000000 500000000 500000000 499317985 499883344 499883344 499883344 499883344 499047944 499814976 499814976 499007908 498442549 498442549 498442549 499164600 499164600 499164600 499164600 500000000 500000000 500000000 500000000
output:
6
result:
ok 1 number(s): "6"
Test #17:
score: 0
Accepted
time: 15ms
memory: 5444kb
input:
23 500578170 501342629 500685333 500685333 500685333 500434440 500434440 500833302 500833302 500018930 500352528 500127753 500603421 501751304 501417793 500685333 500685333 499920874 500578170 500000000 500420306 500420306 500420306
output:
11
result:
ok 1 number(s): "11"
Test #18:
score: 0
Accepted
time: 2091ms
memory: 200316kb
input:
23 501122407 505187190 506309930 504626086 504486924 505864777 505478791 504987294 506389246 504959954 503907177 503951359 504513755 503329719 502108244 500920912 502168527 499084052 499787444 501128474 502585881 500042621 498430594
output:
23
result:
ok 1 number(s): "23"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
23 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 499999978 499999978 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000
output:
2
result:
ok 1 number(s): "2"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
23 500000000 500000000 499999924 499999924 499999952 499999952 500000028 499999983 499999983 500000069 500000069 500000069 500000069 500000069 500000148 500000148 500000069 500000069 500000069 500000000 500000000 500000000 500000000
output:
6
result:
ok 1 number(s): "6"
Test #21:
score: 0
Accepted
time: 15ms
memory: 5368kb
input:
23 500000000 499999969 499999929 499999929 499999779 499999747 499999747 499999747 499999667 499999707 499999930 499999891 499999891 499999881 499999881 499999845 499999925 499999925 499999964 499999964 499999904 499999964 500000000
output:
10
result:
ok 1 number(s): "10"
Test #22:
score: 0
Accepted
time: 2119ms
memory: 200572kb
input:
23 500000155 500000315 500000231 500000048 500000372 500000424 500000278 500000277 500000124 500000103 500000191 499999987 499999852 499999617 499999631 499999629 499999711 499999651 499999585 499999530 499999495 499999747 499999993
output:
19
result:
ok 1 number(s): "19"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
23 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500000000 500006119 500006119 500006119 500006119 500006119 500006119 500000000 500000000 500000000 500000000
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
23 500000000 499991623 499991623 499991623 499991623 499984295 499975156 499975156 499975156 499976321 499976321 499976321 499976321 499993837 499993837 499993837 500001165 500001165 500001165 500000000 500000936 500000936 500000936
output:
6
result:
ok 1 number(s): "6"
Test #25:
score: 0
Accepted
time: 8ms
memory: 6492kb
input:
23 500000000 500002755 500002755 500002067 500002067 500002067 500007059 500007132 500015950 500015950 500010958 499993925 499993925 499995224 499997138 500004895 500004895 499999276 499999276 499996521 500000841 500000841 500000000
output:
11
result:
ok 1 number(s): "11"
Test #26:
score: 0
Accepted
time: 2101ms
memory: 200364kb
input:
23 500009706 500006191 499984915 500014440 500023321 500026011 500039936 500024527 500036349 500046344 500041663 500021759 500032357 500030712 500006508 500019971 500032469 500052348 500028446 500001617 500011492 500019408 500015211
output:
21
result:
ok 1 number(s): "21"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
23 500000000 500000000 500000000 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037 499207037
output:
2
result:
ok 1 number(s): "2"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
23 500000000 500000000 499906417 499906417 499004628 498250213 498250213 498250213 498250213 498250213 498250213 498250213 498326320 498326320 498326320 499004628 499004628 499004628 499098211 499098211 500000000 500000000 500000000
output:
5
result:
ok 1 number(s): "5"
Test #29:
score: 0
Accepted
time: 15ms
memory: 7172kb
input:
23 500000000 499433731 498421805 498421805 498210823 498006549 498006549 498006549 498006549 498587939 498661850 498661850 498291442 498291442 498388735 499246254 500160887 500160887 500903970 501108244 501674513 500857519 500000000
output:
10
result:
ok 1 number(s): "10"
Test #30:
score: 0
Accepted
time: 2070ms
memory: 200504kb
input:
23 498848100 495902575 495746206 496218670 495979695 497212048 498148282 498317731 497827244 497356221 496914395 491578419 489374599 490446554 488473546 490054662 493713401 493738233 495454097 496961762 497102961 498246670 499168534
output:
23
result:
ok 1 number(s): "23"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5
output:
1
result:
ok 1 number(s): "1"
Test #32:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
23 4 0 0 0 3 3 3 9 9 9 9 9 9 9 9 7 7 2 2 2 2 2 0
output:
5
result:
ok 1 number(s): "5"
Test #33:
score: 0
Accepted
time: 2ms
memory: 4044kb
input:
23 0 0 2 0 0 0 2 2 7 6 8 8 8 5 5 0 2 10 2 2 11 9 0
output:
8
result:
ok 1 number(s): "8"
Test #34:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
23 0 0 0 0 0 58 58 58 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
1
result:
ok 1 number(s): "1"
Test #35:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
23 0 0 0 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0
output:
1
result:
ok 1 number(s): "1"
Test #36:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
23 0 26 0 0 0 0 12 12 0 17 17 25 25 25 49 0 0 21 0 0 0 0 0
output:
6
result:
ok 1 number(s): "6"
Test #37:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 387 387 387 387 387 387
output:
1
result:
ok 1 number(s): "1"
Test #38:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
23 0 0 0 0 0 0 0 0 0 471 471 471 0 0 0 0 0 255 255 0 0 0 0
output:
2
result:
ok 1 number(s): "2"
Test #39:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
23 0 39 39 39 0 0 0 0 0 0 0 0 0 0 56 618 618 0 507 507 0 0 0
output:
4
result:
ok 1 number(s): "4"
Test #40:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
12 500000000 500000000 500000000 500000000 500000000 500000000 500000000 499999925 499999925 499999925 500000000 500000000
output:
2
result:
ok 1 number(s): "2"
Test #41:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
12 500000068 500000068 500000068 500000068 500000236 500000236 500000348 500000280 500000280 500000252 500000178 500000094
output:
6
result:
ok 1 number(s): "6"
Test #42:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
12 500000036 500000036 500000094 500000091 500000071 500000180 500000139 500000139 500000081 500000052 500000052 500000066
output:
8
result:
ok 1 number(s): "8"
Test #43:
score: 0
Accepted
time: 1ms
memory: 3996kb
input:
12 500000275 499999911 499999869 499999727 499999605 499999420 499999573 499999445 499999454 499999592 499999536 499999675
output:
11
result:
ok 1 number(s): "11"
Test #44:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
12 500000000 500000000 500000000 500000000 500000000 500000000 500000000 499993913 499993913 500000000 500000000 500000000
output:
2
result:
ok 1 number(s): "2"
Test #45:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
12 500006067 500006067 500006067 499999092 499999092 500004693 499998027 499992426 499985213 499993025 500000000 500000000
output:
6
result:
ok 1 number(s): "6"
Test #46:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
12 500000693 500008328 499994319 499994319 499994319 499988701 499995255 499995255 499996495 500003850 499996215 499996814
output:
8
result:
ok 1 number(s): "8"
Test #47:
score: 0
Accepted
time: 1ms
memory: 4064kb
input:
12 499995758 500029554 500038100 500105274 500056969 500051722 500049028 500006103 500002095 500008779 500012816 500004278
output:
12
result:
ok 1 number(s): "12"
Test #48:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
12 500000000 500808447 500808447 500808447 500808447 500000000 500000000 500000000 500000000 500000000 500000000 500000000
output:
2
result:
ok 1 number(s): "2"
Test #49:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
12 499754295 499754295 499754295 499519818 500429969 500664446 500774079 501489727 500579576 500469943 500469943 500000000
output:
6
result:
ok 1 number(s): "6"
Test #50:
score: 0
Accepted
time: 1ms
memory: 3956kb
input:
12 499117991 498271666 499225658 499225658 499487368 500063644 499528612 500410621 501005234 500204419 499960542 499789532
output:
10
result:
ok 1 number(s): "10"
Test #51:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
12 501960621 504050777 504603727 504435368 501735026 502850106 501772052 498494818 494609715 495382734 496351255 499241585
output:
12
result:
ok 1 number(s): "12"
Test #52:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
0
result:
ok 1 number(s): "0"