QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #344279 | #7566. Interval Addition | Alish | AC ✓ | 1122ms | 71204kb | C++17 | 1.0kb | 2024-03-03 22:26:29 | 2024-03-03 22:26:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define Mp make_pair
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("tests.in" , "r" , stdin) ;
ll mod = 1e9+7 ;
const int N = 25;
int n;
int a[N], b[N];
int dp[1<<N];
int main()
{
fast_io
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i];
n++;
for (int i=1; i<=n; i++) b[i-1]=a[i]-a[i-1];
for (int mask=1; mask<(1<<n); mask++){
ll sum=0;
dp[mask]=N;
for (int i=0; i<n; i++) if(mask>>i&1){
sum+=b[i];
dp[mask]=min(dp[mask], dp[mask^(1<<i)]);
}
if(sum)dp[mask]++;
}
cout<<dp[(1<<n)-1]<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
5 1 2 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
6 1 1 4 5 1 4
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1052ms
memory: 69500kb
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: 1050ms
memory: 70332kb
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: 0ms
memory: 3636kb
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: 3636kb
input:
1 46422493
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 1101ms
memory: 69388kb
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: 1048ms
memory: 69808kb
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: 1040ms
memory: 71080kb
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: 1053ms
memory: 70024kb
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: 1122ms
memory: 70940kb
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: 1045ms
memory: 69544kb
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: 1048ms
memory: 69568kb
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: 1049ms
memory: 69744kb
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: 1057ms
memory: 71204kb
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: 1041ms
memory: 70268kb
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: 1061ms
memory: 69576kb
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: 1051ms
memory: 71032kb
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: 1112ms
memory: 70924kb
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: 1042ms
memory: 70476kb
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: 1040ms
memory: 70164kb
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: 1059ms
memory: 70100kb
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: 1107ms
memory: 70252kb
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: 1035ms
memory: 70016kb
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: 1047ms
memory: 69320kb
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: 1053ms
memory: 70084kb
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: 1058ms
memory: 70592kb
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: 1041ms
memory: 69408kb
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: 1040ms
memory: 70892kb
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: 1055ms
memory: 71120kb
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: 1047ms
memory: 69380kb
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: 1038ms
memory: 70864kb
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: 1030ms
memory: 70772kb
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: 1012ms
memory: 69680kb
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: 1032ms
memory: 70808kb
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: 1044ms
memory: 69176kb
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: 1033ms
memory: 69564kb
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: 1029ms
memory: 71084kb
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: 1048ms
memory: 69604kb
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: 3708kb
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: 3544kb
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: 3688kb
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: 3692kb
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: 3660kb
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: 3636kb
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: 3600kb
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: 3660kb
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: 3684kb
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: 1ms
memory: 3644kb
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: 3736kb
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: 3708kb
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: 1050ms
memory: 70176kb
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"