QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #234175 | #7566. Interval Addition | Edwin_VanCleef | AC ✓ | 2058ms | 397080kb | C++14 | 1.8kb | 2023-11-01 14:42:35 | 2023-11-01 14:42:35 |
Judging History
answer
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
namespace my_IO{
#define ll long long
#define ull unsigned long long
#define ld long double
#define spc putchar(' ')
#define et putchar('\n')
template<class T>
void read(T &num){
T x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<3)+(x<<1)+c-48;
c=getchar();
}
num=f*x;
}
template<class T>
void write(T x){
static char buf[40];
static int len=-1;
if(x<0) putchar('-'),x=-x;
do{
buf[++len]=x%10+48;
x/=10;
}while(x);
while(len>=0) putchar(buf[len--]);
}
}
using namespace my_IO;
const ll inf=1e9;
const ll maxn=25;
ll n,a[maxn],b[maxn],f[1<<24],pos[maxn],bk[maxn],pre[1<<24],vis[1<<24],cnt[1<<24];
void solve(){
read(n);
for(ll i=0;i<1<<(n+1);++i) cnt[i]=__builtin_popcount(i);
for(ll i=1;i<=n;++i){
read(a[i]);
b[i]=a[i]-a[i-1];
}
b[n+1]=-a[n];
for(ll s=1;s<1<<(n+1);++s){
ll sum=0,flag=1;
for(ll i=1;i<=n+1;++i){
if(s&(1<<(i-1))){
sum+=b[i];
if(sum<0){
flag=0;
break;
}
}
}
if(!flag) continue;
if(!sum) vis[s]=1;
}
f[0]=0;
for(ll s=1;s<1<<(n+1);++s){
if(vis[s]) ++f[s];
for(ll j=1;j<=n+1;++j){
if(!(s&(1<<(j-1)))){
f[s|(1<<(j-1))]=max(f[s|(1<<(j-1))],f[s]);
}
}
}
write(n+1-f[(1<<(n+1))-1]);
}
int main(){
int t=1;
while(t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7720kb
input:
5 1 2 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7724kb
input:
6 1 1 4 5 1 4
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1314ms
memory: 265684kb
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: 1340ms
memory: 268296kb
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: 7668kb
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: 7728kb
input:
1 46422493
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 1825ms
memory: 364080kb
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: 1979ms
memory: 281892kb
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: 1873ms
memory: 271200kb
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: 1611ms
memory: 283192kb
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: 2034ms
memory: 335316kb
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: 1742ms
memory: 282600kb
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: 1704ms
memory: 266676kb
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: 1626ms
memory: 265960kb
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: 1877ms
memory: 396836kb
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: 1675ms
memory: 288276kb
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: 1704ms
memory: 267236kb
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: 1809ms
memory: 265704kb
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: 1865ms
memory: 355812kb
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: 1704ms
memory: 298512kb
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: 1538ms
memory: 271844kb
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: 1675ms
memory: 285144kb
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: 1986ms
memory: 335220kb
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: 1636ms
memory: 290576kb
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: 1903ms
memory: 310704kb
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: 1627ms
memory: 309332kb
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: 1751ms
memory: 397040kb
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: 1620ms
memory: 337356kb
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: 1570ms
memory: 310560kb
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: 1559ms
memory: 269804kb
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: 2025ms
memory: 343992kb
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: 1715ms
memory: 366736kb
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: 1677ms
memory: 322616kb
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: 1738ms
memory: 396776kb
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: 1986ms
memory: 359372kb
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: 1632ms
memory: 322540kb
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: 1974ms
memory: 352116kb
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: 1990ms
memory: 351400kb
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: 1778ms
memory: 320268kb
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: 7716kb
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: 1ms
memory: 7716kb
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: 1ms
memory: 7688kb
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: 7696kb
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: 1ms
memory: 7756kb
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: 1ms
memory: 8020kb
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: 1ms
memory: 7948kb
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: 7784kb
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: 1ms
memory: 7988kb
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: 2ms
memory: 12116kb
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: 2ms
memory: 11824kb
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: 0ms
memory: 7716kb
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: 2058ms
memory: 397080kb
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"