# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
62199 | 2018-07-27T20:05:09 Z | qkxwsm | Stove (JOI18_stove) | C++17 | 40 ms | 10768 KB |
/* PROG: source LANG: C++11 _____ .' '. / 0 0 \ | ^ | | \ / | \ '---' / '._____.' */ #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; struct chash { int operator()(int x) const { x ^= (x >> 20) ^ (x >> 12); return x ^ (x >> 7) ^ (x >> 4); } int operator()(long long x) const { return x ^ (x >> 32); } }; template<typename T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using hashtable = gp_hash_table<T, T, chash>; template<class T> void readi(T &x) { T input = 0; bool negative = false; char c = ' '; while (c < '-') { c = getchar(); } if (c == '-') { negative = true; c = getchar(); } while (c >= '0') { input = input * 10 + (c - '0'); c = getchar(); } if (negative) { input = -input; } x = input; } template<class T> void printi(T output) { if (output == 0) { putchar('0'); return; } if (output < 0) { putchar('-'); output = -output; } int aout[20]; int ilen = 0; while(output) { aout[ilen] = ((output % 10)); output /= 10; ilen++; } for (int i = ilen - 1; i >= 0; i--) { putchar(aout[i] + '0'); } return; } template<class T> void ckmin(T &a, T b) { a = min(a, b); } template<class T> void ckmax(T &a, T b) { a = max(a, b); } template<class T> T normalize(T x, T mod = 1000000007) { return (((x % mod) + mod) % mod); } long long randomizell(long long mod) { return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod; } int randomize(int mod) { return ((1ll << 15) * rand() + rand()) % mod; } #define y0 ___y0 #define y1 ___y1 #define MP make_pair #define MT make_tuple #define PB push_back #define PF push_front #define LB lower_bound #define UB upper_bound #define fi first #define se second #define debug(x) cerr << #x << " = " << x << endl; const long double PI = 4.0 * atan(1.0); const long double EPS = 1e-10; #define MAGIC 347 #define SINF 10007 #define CO 1000007 #define INF 1000000007 #define BIG 1000000931 #define LARGE 1696969696967ll #define GIANT 2564008813937411ll #define LLINF 2696969696969696969ll #define MAXN 100013 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ld, ld> pdd; int N, K; int arr[MAXN]; vector<int> inc; int ans; int32_t main() { ios_base::sync_with_stdio(0); srand(time(0)); // cout << fixed << setprecision(10); // cerr << fixed << setprecision(10); if (fopen("input.in", "r")) { freopen ("input.in", "r", stdin); freopen ("output.out", "w", stdout); } cin >> N >> K; for (int i = 0; i < N; i++) { cin >> arr[i]; } for (int i = 1; i < N; i++) { inc.PB(arr[i] - arr[i - 1] - 1); } sort(inc.begin(), inc.end()); ans = N; for (int i = 0; i < N - K; i++) { ans += inc[i]; } cout << ans << '\n'; // cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 500 KB | Output is correct |
3 | Correct | 3 ms | 508 KB | Output is correct |
4 | Correct | 3 ms | 512 KB | Output is correct |
5 | Correct | 3 ms | 604 KB | Output is correct |
6 | Correct | 3 ms | 612 KB | Output is correct |
7 | Correct | 3 ms | 656 KB | Output is correct |
8 | Correct | 3 ms | 744 KB | Output is correct |
9 | Correct | 3 ms | 764 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 500 KB | Output is correct |
3 | Correct | 3 ms | 508 KB | Output is correct |
4 | Correct | 3 ms | 512 KB | Output is correct |
5 | Correct | 3 ms | 604 KB | Output is correct |
6 | Correct | 3 ms | 612 KB | Output is correct |
7 | Correct | 3 ms | 656 KB | Output is correct |
8 | Correct | 3 ms | 744 KB | Output is correct |
9 | Correct | 3 ms | 764 KB | Output is correct |
10 | Correct | 5 ms | 764 KB | Output is correct |
11 | Correct | 4 ms | 784 KB | Output is correct |
12 | Correct | 4 ms | 832 KB | Output is correct |
13 | Correct | 4 ms | 880 KB | Output is correct |
14 | Correct | 5 ms | 928 KB | Output is correct |
15 | Correct | 4 ms | 976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 500 KB | Output is correct |
3 | Correct | 3 ms | 508 KB | Output is correct |
4 | Correct | 3 ms | 512 KB | Output is correct |
5 | Correct | 3 ms | 604 KB | Output is correct |
6 | Correct | 3 ms | 612 KB | Output is correct |
7 | Correct | 3 ms | 656 KB | Output is correct |
8 | Correct | 3 ms | 744 KB | Output is correct |
9 | Correct | 3 ms | 764 KB | Output is correct |
10 | Correct | 5 ms | 764 KB | Output is correct |
11 | Correct | 4 ms | 784 KB | Output is correct |
12 | Correct | 4 ms | 832 KB | Output is correct |
13 | Correct | 4 ms | 880 KB | Output is correct |
14 | Correct | 5 ms | 928 KB | Output is correct |
15 | Correct | 4 ms | 976 KB | Output is correct |
16 | Correct | 29 ms | 2928 KB | Output is correct |
17 | Correct | 28 ms | 3892 KB | Output is correct |
18 | Correct | 40 ms | 4856 KB | Output is correct |
19 | Correct | 38 ms | 5820 KB | Output is correct |
20 | Correct | 29 ms | 6784 KB | Output is correct |
21 | Correct | 40 ms | 7748 KB | Output is correct |
22 | Correct | 32 ms | 8840 KB | Output is correct |
23 | Correct | 29 ms | 9676 KB | Output is correct |
24 | Correct | 31 ms | 10768 KB | Output is correct |