Task: | Programmers |
Sender: | MAKMED1337 |
Submission time: | 2021-01-30 23:00:14 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 34 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 34 |
#2 | RUNTIME ERROR | 0 |
#3 | RUNTIME ERROR | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#12 | ACCEPTED | 0.02 s | 1, 3 | details |
#13 | ACCEPTED | 0.02 s | 1, 3 | details |
#14 | ACCEPTED | 0.03 s | 1, 3 | details |
#15 | ACCEPTED | 0.01 s | 1, 3 | details |
#16 | ACCEPTED | 0.04 s | 1, 3 | details |
#17 | ACCEPTED | 0.40 s | 2, 3 | details |
#18 | RUNTIME ERROR | 0.34 s | 2, 3 | details |
#19 | RUNTIME ERROR | 0.34 s | 2, 3 | details |
#20 | RUNTIME ERROR | 0.33 s | 2, 3 | details |
#21 | RUNTIME ERROR | 0.34 s | 2, 3 | details |
#22 | RUNTIME ERROR | 0.33 s | 2, 3 | details |
#23 | RUNTIME ERROR | 0.33 s | 2, 3 | details |
#24 | RUNTIME ERROR | 0.44 s | 3 | details |
#25 | RUNTIME ERROR | 0.45 s | 3 | details |
#26 | RUNTIME ERROR | 0.45 s | 3 | details |
#27 | RUNTIME ERROR | 0.45 s | 3 | details |
#28 | RUNTIME ERROR | 0.45 s | 3 | details |
#29 | RUNTIME ERROR | 0.45 s | 3 | details |
#30 | RUNTIME ERROR | 0.45 s | 3 | details |
#31 | RUNTIME ERROR | 0.46 s | 3 | details |
Code
#include <bits/stdc++.h>#include <climits>using namespace std;template<class T>using V = vector<T>;template<class T>using VV = V<V<T>>;using ld = long double;#define ll long longusing ull = unsigned ll;using PLL = pair<ll, ll>;using VLL = V<ll>;using VB = V<bool>;using VVB = VV<bool>;using VVLL = VV<ll>;using Gr = VVLL;using MLL = map<ll, ll>;#define UMLL unordered_map<ll, ll, custom_hash>//using int128 = __int128;//using double128 = __float128;#define fast ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); cerr.tie(nullptr);#define INF 100000000000000#define MINF LONG_MIN#define R &#define CR const R#define FORI(i, a, b) for(ll i = a, max##i = b; i < max##i; ++i)#define FOR(i, n) FORI(i, 0, n)#define RFORI(i, a, b) for(ll i = a, min##i = b; i >= min##i; --i)#define RFOR(i, n) RFORI(i, n, 0)#define FORA(i, a) for(auto i : a)#define FORAR(i, a) for(auto R i : a)#define FORACR(i, a) for(auto CR i : a)#define ALL(obj) begin(obj), end(obj)#define Count(q) while(q--)#define OK cerr << "OK\n";#define mp make_pair#define pb push_back//#define DEBUGtemplate<class T>T sqr(T x){return x * x;}void YES(bool g, ostream R os, bool upper = true){if(g)if(upper)os << "YES";elseos << "Yes";elseif(upper)os << "NO";elseos << "No";os << "\n";}template<class T>void show(T CR t, ostream R os = cerr){FORACR(i, t)os << i << " ";os << "\n";}template<class T>void show2d(T CR t, ostream R os = cerr){FORACR(i, t)show(i, os);os << "\n";}constexpr ll MOD = 1e9 + 7;//constexpr ll len = 40320 + 1;constexpr ld PI = atanl(1.0L) * 4;struct custom_hash{static uint64_t splitmix64(uint64_t x){x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}size_t operator() (uint64_t x) const{static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};//arrvoid init() {}void solve(istream R is, ostream R os){ll n, k;is >> n >> k;VLL a(n);FORAR(i, a)is >> i;MLL m;FORACR(i, a)++m[i];V<PLL> b;FORACR(i, m)b.pb(i);n = b.size();V<VVLL> dp(2, VVLL(n, VLL(k + 1, INF)));ll d = min(b[0].second / 2, k);FOR(i, d + 1)dp[0][0][i] = 0;d = min((b[0].second - 1) / 2, k);FOR(i, d + 1)dp[1][0][i] = 0;FORI(i, 1, n){//cerr << i << "\t" << b[i].first << " " << b[i].second << "\n";ll t = b[i].second;//i + t / 2 < k + 1//i < k + 1 - t / 2FOR(j, k + 1){ll x = 0;if(j - t / 2 >= 0)x = dp[0][i - 1][j - t / 2];ll y = 0;if(j - (1 + (t - 1) / 2) >= 0)y = dp[1][i - 1][j - (1 + (t - 1) / 2)] + b[i].first - b[i - 1].first;if(t == 0)y = INF;dp[0][i][j] = min(x, y);}--t;FOR(j, k + 1){ll x = 0;if(j - t / 2 >= 0)x = dp[0][i - 1][j - t / 2];ll y = 0;if(j - (1 + (t - 1) / 2) >= 0)y = dp[1][i - 1][j - (1 + (t - 1) / 2)] + b[i].first - b[i - 1].first;if(t == 0)y = INF;dp[1][i][j] = min(x, y);}}os << min(dp[0][n - 1][k], dp[1][n - 1][k]) << "\n";}void tester(istream R is, ostream R os){fastinit();ll q = 1;//is >> q;os << setprecision(999);Count(q)solve(is, os);}int main(){//ifstream in("input.txt");//ofstream out("output.txt");tester(cin, cout);}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
8 3 3 1 2 7 9 3 4 7 |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2 1 2 13 |
correct output |
---|
11 |
user output |
---|
11 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
20 10 16 20 6 15 19 12 11 17 20 6 15... |
correct output |
---|
6 |
user output |
---|
6 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
14 5 11 3 8 3 14 8 10 13 11 10 17 1... |
correct output |
---|
0 |
user output |
---|
0 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
15 1 8 5 1 8 18 15 6 20 14 9 10 9 1... |
correct output |
---|
0 |
user output |
---|
0 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 3 10 19 16 15 12 5 14 8 3 15 |
correct output |
---|
4 |
user output |
---|
4 |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
202 90 177 187 183 647 616 580 499 78... |
correct output |
---|
213 |
user output |
---|
213 |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2000 512 141 583 135 833 900 308 248 58... |
correct output |
---|
0 |
user output |
---|
0 |
Test 9
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2000 972 685 4 289 865 93 159 48 866 56... |
correct output |
---|
276 |
user output |
---|
276 |
Test 10
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2000 1000 698 153 298 118 631 341 238 7 ... |
correct output |
---|
517 |
user output |
---|
517 |
Test 11
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2000 1 983 144 449 584 839 166 77 885... |
correct output |
---|
0 |
user output |
---|
0 |
Test 12
Group: 1, 3
Verdict: ACCEPTED
input |
---|
1464 320 846762124 954854396 12767390 7... |
correct output |
---|
35809369 |
user output |
---|
35809369 |
Test 13
Group: 1, 3
Verdict: ACCEPTED
input |
---|
2000 231 801945178 924940258 369188694 ... |
correct output |
---|
7831421 |
user output |
---|
7831421 |
Test 14
Group: 1, 3
Verdict: ACCEPTED
input |
---|
2000 461 464790475 932031556 838378103 ... |
correct output |
---|
37272564 |
user output |
---|
37272564 |
Test 15
Group: 1, 3
Verdict: ACCEPTED
input |
---|
2000 100 484046702 267135814 995006323 ... |
correct output |
---|
1268400 |
user output |
---|
1268400 |
Test 16
Group: 1, 3
Verdict: ACCEPTED
input |
---|
2000 996 98352148 438929491 242618159 1... |
correct output |
---|
445965905 |
user output |
---|
445965905 |
Test 17
Group: 2, 3
Verdict: ACCEPTED
input |
---|
65879 19675 896 316 972 476 636 227 716 78... |
correct output |
---|
0 |
user output |
---|
0 |
Test 18
Group: 2, 3
Verdict: RUNTIME ERROR
input |
---|
200000 53820 995 720 135 767 943 742 191 26... |
correct output |
---|
0 |
user output |
---|
(empty) |
Test 19
Group: 2, 3
Verdict: RUNTIME ERROR
input |
---|
200000 32297 527 947 84 851 908 833 339 112... |
correct output |
---|
0 |
user output |
---|
(empty) |
Test 20
Group: 2, 3
Verdict: RUNTIME ERROR
input |
---|
200000 99982 561 174 242 275 460 109 664 68... |
correct output |
---|
322 |
user output |
---|
(empty) |
Test 21
Group: 2, 3
Verdict: RUNTIME ERROR
input |
---|
200000 99955 911 33 314 861 298 117 972 982... |
correct output |
---|
245 |
user output |
---|
(empty) |
Test 22
Group: 2, 3
Verdict: RUNTIME ERROR
input |
---|
200000 99972 783 1000 673 611 87 452 702 92... |
correct output |
---|
290 |
user output |
---|
(empty) |
Test 23
Group: 2, 3
Verdict: RUNTIME ERROR
input |
---|
200000 99961 795 136 128 643 60 422 371 839... |
correct output |
---|
252 |
user output |
---|
(empty) |
Test 24
Group: 3
Verdict: RUNTIME ERROR
input |
---|
195426 76599 442872072 619088799 118541378 ... |
correct output |
---|
143376538 |
user output |
---|
(empty) |
Test 25
Group: 3
Verdict: RUNTIME ERROR
input |
---|
200000 1661 894106972 620084612 931442312 ... |
correct output |
---|
33089 |
user output |
---|
(empty) |
Test 26
Group: 3
Verdict: RUNTIME ERROR
input |
---|
200000 86032 211444153 846442677 297198384 ... |
correct output |
---|
196001810 |
user output |
---|
(empty) |
Test 27
Group: 3
Verdict: RUNTIME ERROR
input |
---|
200000 28275 28280312 349705372 96535649 84... |
correct output |
---|
11627219 |
user output |
---|
(empty) |
Test 28
Group: 3
Verdict: RUNTIME ERROR
input |
---|
200000 81473 178022892 112774306 250584651 ... |
correct output |
---|
162430841 |
user output |
---|
(empty) |
Test 29
Group: 3
Verdict: RUNTIME ERROR
input |
---|
200000 99987 297598052 494409138 182268523 ... |
correct output |
---|
489497036 |
user output |
---|
(empty) |
Test 30
Group: 3
Verdict: RUNTIME ERROR
input |
---|
200000 99971 316462272 843156468 434342923 ... |
correct output |
---|
483167476 |
user output |
---|
(empty) |
Test 31
Group: 3
Verdict: RUNTIME ERROR
input |
---|
200000 99964 811543559 465033274 620180191 ... |
correct output |
---|
481497328 |
user output |
---|
(empty) |