CSES - KILO 2017 1/5

Submission details
Task:	Queue
Sender:	Semikolonisti
Submission time:	2017-09-05 18:48:38 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.05 s	details
#2	ACCEPTED	0.04 s	details
#3	ACCEPTED	0.03 s	details
#4	ACCEPTED	0.04 s	details
#5	ACCEPTED	0.05 s	details
#6	ACCEPTED	0.04 s	details
#7	ACCEPTED	0.05 s	details
#8	ACCEPTED	0.03 s	details
#9	ACCEPTED	0.04 s	details
#10	ACCEPTED	0.04 s	details
#11	ACCEPTED	0.04 s	details
#12	ACCEPTED	0.04 s	details
#13	ACCEPTED	0.04 s	details
#14	ACCEPTED	0.03 s	details
#15	ACCEPTED	0.04 s	details
#16	ACCEPTED	0.06 s	details
#17	ACCEPTED	0.06 s	details
#18	ACCEPTED	0.04 s	details
#19	ACCEPTED	0.06 s	details
#20	ACCEPTED	0.05 s	details
#21	ACCEPTED	0.04 s	details
#22	ACCEPTED	0.06 s	details
#23	ACCEPTED	0.06 s	details
#24	ACCEPTED	0.05 s	details
#25	ACCEPTED	0.05 s	details
#26	ACCEPTED	0.08 s	details
#27	ACCEPTED	0.04 s	details
#28	ACCEPTED	0.05 s	details
#29	ACCEPTED	0.09 s	details
#30	ACCEPTED	0.07 s	details
#31	ACCEPTED	0.03 s	details
#32	ACCEPTED	0.05 s	details
#33	ACCEPTED	0.04 s	details
#34	ACCEPTED	0.04 s	details
#35	ACCEPTED	0.05 s	details
#36	ACCEPTED	0.04 s	details
#37	ACCEPTED	0.04 s	details
#38	ACCEPTED	0.04 s	details
#39	ACCEPTED	0.04 s	details
#40	ACCEPTED	0.05 s	details
#41	ACCEPTED	0.12 s	details
#42	ACCEPTED	0.10 s	details
#43	ACCEPTED	0.08 s	details
#44	ACCEPTED	0.07 s	details
#45	ACCEPTED	0.06 s	details
#46	ACCEPTED	0.12 s	details
#47	ACCEPTED	0.11 s	details
#48	ACCEPTED	0.06 s	details
#49	ACCEPTED	0.12 s	details
#50	ACCEPTED	0.10 s	details
#51	ACCEPTED	0.10 s	details
#52	ACCEPTED	0.14 s	details
#53	ACCEPTED	0.08 s	details
#54	ACCEPTED	0.07 s	details
#55	ACCEPTED	0.05 s	details
#56	ACCEPTED	0.14 s	details
#57	ACCEPTED	0.09 s	details
#58	ACCEPTED	0.07 s	details
#59	ACCEPTED	0.14 s	details
#60	ACCEPTED	0.10 s	details

Code

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define M 1000000007
#define pii pair<ll, ll>

using namespace std;

ll s[2222];
ll l[2222];
ll dp[100001];

int main () {
    cin.sync_with_stdio(false);
    cin.tie(0);
    ll n, m, asd;
    cin>>n>>m>>asd;
    for (int i = 1; i <= n; i++) {
        int a;
        cin>>a;
        s[a]++;
        l[a] = i;
    }
    pii p[m];
    for (int i = 0; i < m; i++) {
        p[i] = {l[i + 1], i + 1};
    }
    sort(p, p + m);
    ll mx = 0;
    dp[0] = 1;
    ll ans = 1000000000000000LL;
    for (ll i = 0; i < m; i++) {
        ll k = s[p[i].S];
        for (ll j = min(asd, mx + k); j >= k; j--) {
            if (!dp[j] && dp[j - k]) {
                dp[j] = l[p[i].S];
                if (n - j <= asd) ans = min(ans, dp[j] * j + n * (n - j));
                mx = max(mx, j);
            }
        }
    }
    if (ans != 1000000000000000LL) cout<<ans<<endl;
    else cout<<-1<<endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
`4 3 2 1 1 1 1` view save

correct output
`-1` view save

user output
`-1` view save

Test 2

Verdict: ACCEPTED

input
`6 6 5 2 1 2 2 2 1` view save

correct output
`32` view save

user output
`32` view save

Test 3

Verdict: ACCEPTED

input
`3 2 3 1 1 1` view save

correct output
`9` view save

user output
`9` view save

Test 4

Verdict: ACCEPTED

input
`3 1 3 1 1 1` view save

correct output
`9` view save

user output
`9` view save

Test 5

Verdict: ACCEPTED

input
`2 2 2 1 2` view save

correct output
`3` view save

user output
`3` view save

Test 6

Verdict: ACCEPTED

input
`10 9 5 1 1 1 1 2 9 9 9 9 9` view save

correct output
`75` view save

user output
`75` view save

Test 7

Verdict: ACCEPTED

input
`8 2 7 1 1 1 1 1 2 2 2` view save

correct output
`49` view save

user output
`49` view save

Test 8

Verdict: ACCEPTED

input
`10 6 7 1 1 1 1 1 1 6 6 6 6` view save

correct output
`76` view save

user output
`76` view save

Test 9

Verdict: ACCEPTED

input
`6 3 4 3 3 3 3 2 3` view save

correct output
`-1` view save

user output
`-1` view save

Test 10

Verdict: ACCEPTED

input
`3 3 2 1 1 1` view save

correct output
`-1` view save

user output
`-1` view save

Test 11

Verdict: ACCEPTED

input
`43893 9 34336 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1498448497` view save

user output
`1498448497` view save

Test 12

Verdict: ACCEPTED

input
`17481 8 11137 3 2 5 2 6 1 8 6 1 6 1 7 5 1 1 ...` view save

correct output
`305552418` view save

user output
`305552418` view save

Test 13

Verdict: ACCEPTED

input
`28826 9 20049 1 1 3 1 1 3 1 2 1 1 2 1 2 1 1 ...` view save

correct output
`830887525` view save

user output
`830887525` view save

Test 14

Verdict: ACCEPTED

input
`39533 8 27095 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...` view save

correct output
`-1` view save

user output
`-1` view save

Test 15

Verdict: ACCEPTED

input
`71270 6 53774 4 4 1 2 6 1 1 6 4 3 1 2 5 5 5 ...` view save

correct output
`-1` view save

user output
`-1` view save

Test 16

Verdict: ACCEPTED

input
`41203 8 24337 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1320922405` view save

user output
`1320922405` view save

Test 17

Verdict: ACCEPTED

input
`47138 7 40668 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1671316774` view save

user output
`1671316774` view save

Test 18

Verdict: ACCEPTED

input
`7651 7 4893 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`43907177` view save

user output
`43907177` view save

Test 19

Verdict: ACCEPTED

input
`34482 4 23135 4 1 2 2 2 3 3 2 2 1 1 3 4 1 1 ...` view save

correct output
`1188973626` view save

user output
`1188973626` view save

Test 20

Verdict: ACCEPTED

input
`55403 4 28518 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`-1` view save

user output
`-1` view save

Test 21

Verdict: ACCEPTED

input
`32814 412 28236 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`963667791` view save

user output
`963667791` view save

Test 22

Verdict: ACCEPTED

input
`26243 357 18652 181 4 163 158 15 132 2 75 127 ...` view save

correct output
`685896169` view save

user output
`685896169` view save

Test 23

Verdict: ACCEPTED

input
`41483 1432 33362 25 33 220 218 134 4 129 165 26...` view save

correct output
`1712939621` view save

user output
`1712939621` view save

Test 24

Verdict: ACCEPTED

input
`47007 1501 42152 108 21 18 106 68 67 18 39 46 2...` view save

correct output
`2206183867` view save

user output
`2206183867` view save

Test 25

Verdict: ACCEPTED

input
`83160 244 71321 173 221 90 62 126 105 108 183 ...` view save

correct output
`6908701076` view save

user output
`6908701076` view save

Test 26

Verdict: ACCEPTED

input
`75458 761 55759 6 4 8 4 9 32 15 42 21 4 9 7 6 ...` view save

correct output
`4361407820` view save

user output
`4361407820` view save

Test 27

Verdict: ACCEPTED

input
`35163 867 24205 1 1 4 4 1 2 2 1 1 1 1 1 1 2 6 ...` view save

correct output
`927749839` view save

user output
`927749839` view save

Test 28

Verdict: ACCEPTED

input
`20899 1205 20082 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`327576151` view save

user output
`327576151` view save

Test 29

Verdict: ACCEPTED

input
`52868 1263 34676 874 8 846 137 306 1005 349 632...` view save

correct output
`2770414204` view save

user output
`2770414204` view save

Test 30

Verdict: ACCEPTED

input
`6634 1439 6197 1 1 1 1 1 1 1 1 1 1 1 1 1 1 12...` view save

correct output
`38501796` view save

user output
`38501796` view save

Test 31

Verdict: ACCEPTED

input
`984 524 694 1 1 1 1 1 1 103 447 47 46 302 ...` view save

correct output
`826296` view save

user output
`826296` view save

Test 32

Verdict: ACCEPTED

input
`351 263 185 17 123 178 84 19 41 70 70 174 ...` view save

correct output
`107763` view save

user output
`107763` view save

Test 33

Verdict: ACCEPTED

input
`2607 363 1692 105 111 52 81 33 41 82 88 43 7...` view save

correct output
`6677793` view save

user output
`6677793` view save

Test 34

Verdict: ACCEPTED

input
`1896 65 1326 1 11 4 1 2 2 4 4 1 1 5 3 1 3 2...` view save

correct output
`3589614` view save

user output
`3589614` view save

Test 35

Verdict: ACCEPTED

input
`1435 19 770 2 6 11 2 18 19 19 12 17 12 12 ...` view save

correct output
`-1` view save

user output
`-1` view save

Test 36

Verdict: ACCEPTED

input
`2014 961 1228 18 41 4 6 31 8 9 6 47 55 1 9 4...` view save

correct output
`3052817` view save

user output
`3052817` view save

Test 37

Verdict: ACCEPTED

input
`2510 863 1932 1 9 1 1 3 3 1 1 2 1 2 6 6 1 2 ...` view save

correct output
`4725076` view save

user output
`4725076` view save

Test 38

Verdict: ACCEPTED

input
`2279 800 2005 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`3895381` view save

user output
`3895381` view save

Test 39

Verdict: ACCEPTED

input
`3044 1282 2850 231 1226 166 709 882 1231 1041...` view save

correct output
`8304793` view save

user output
`8304793` view save

Test 40

Verdict: ACCEPTED

input
`1560 1559 1482 1 1 1 1 579 629 68 256 1543 10...` view save

correct output
`2036808` view save

user output
`2036808` view save

Test 41

Verdict: ACCEPTED

input
`100000 2000 78605 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`8957965216` view save

user output
`8957965216` view save

Test 42

Verdict: ACCEPTED

input
`100000 2000 94147 325 343 6 1583 1423 143 710 43...` view save

correct output
`9938031990` view save

user output
`9938031990` view save

Test 43

Verdict: ACCEPTED

input
`100000 2000 65865 458 353 288 679 148 706 164 58...` view save

correct output
`9972374542` view save

user output
`9972374542` view save

Test 44

Verdict: ACCEPTED

input
`100000 2000 53937 106 33 37 110 24 8 10 25 171 7...` view save

correct output
`9993018364` view save

user output
`9993018364` view save

Test 45

Verdict: ACCEPTED

input
`100000 2000 89553 529 222 626 1397 1697 910 1394...` view save

correct output
`9764828240` view save

user output
`9764828240` view save

Test 46

Verdict: ACCEPTED

input
`100000 2000 83767 25 17 88 123 18 34 4 111 1 7 1...` view save

correct output
`7631468065` view save

user output
`7631468065` view save

Test 47

Verdict: ACCEPTED

input
`100000 2000 86917 3 7 1 1 6 1 11 2 2 1 9 2 10 1 ...` view save

correct output
`7504708607` view save

user output
`7504708607` view save

Test 48

Verdict: ACCEPTED

input
`100000 2000 93483 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 ...` view save

correct output
`7500000000` view save

user output
`7500000000` view save

Test 49

Verdict: ACCEPTED

input
`100000 2000 54022 491 448 31 519 1204 1123 1050 ...` view save

correct output
`9926723265` view save

user output
`9926723265` view save

Test 50

Verdict: ACCEPTED

input
`100000 2000 76351 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`8965046209` view save

user output
`8965046209` view save

Test 51

Verdict: ACCEPTED

input
`100000 2000 88758 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`8953639248` view save

user output
`8953639248` view save

Test 52

Verdict: ACCEPTED

input
`100000 2000 76483 813 438 96 1605 334 27 1280 76...` view save

correct output
`9940504263` view save

user output
`9940504263` view save

Test 53

Verdict: ACCEPTED

input
`100000 2000 66902 8 663 43 227 365 376 315 61 49...` view save

correct output
`9972854726` view save

user output
`9972854726` view save

Test 54

Verdict: ACCEPTED

input
`100000 2000 78996 126 6 55 50 171 68 98 53 164 1...` view save

correct output
`9990578620` view save

user output
`9990578620` view save

Test 55

Verdict: ACCEPTED

input
`100000 2000 57456 552 543 1137 875 1129 1105 116...` view save

correct output
`9995460868` view save

user output
`9995460868` view save

Test 56

Verdict: ACCEPTED

input
`100000 2000 94581 66 8 30 11 5 10 20 28 7 1 207 ...` view save

correct output
`7623200605` view save

user output
`7623200605` view save

Test 57

Verdict: ACCEPTED

input
`100000 2000 99344 2 2 15 10 1 3 15 4 1 3 3 8 2 1...` view save

correct output
`7503153298` view save

user output
`7503153298` view save

Test 58

Verdict: ACCEPTED

input
`100000 2000 52595 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 ...` view save

correct output
`7500000009` view save

user output
`7500000009` view save

Test 59

Verdict: ACCEPTED

input
`100000 2000 90834 478 937 1119 766 1425 368 1620...` view save

correct output
`9924835834` view save

user output
`9924835834` view save

Test 60

Verdict: ACCEPTED

input
`100000 2000 94089 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`8950028575` view save

user output
`8950028575` view save

KILO 2017 1/5

Queue

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Tasks

Submissions (Semikolonisti)