# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
524487 |
2022-02-09T09:35:43 Z |
cqtshadow |
Stove (JOI18_stove) |
C++14 |
|
161 ms |
196420 KB |
#include <bits/stdc++.h>
#define MASK(x) (1LL << x)
#define GETBIT(mask, x) ((mask >> (x))&1)
#define ONBIT(mask, x) (mask | (1LL << (x)))
#define Each(type, i, a, b) for(type i = (a) ; i <= (b) ; ++i)
#define REach(type, i, a, b) for(type i = (a) ; i >= (b) ; --i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const double eps = 1e-9;
const ll oo = 4e18;
template<class X> bool maximize(X &x, X y) {return (x + eps < y ? x = y, true : false);}
template<class X> bool minimize(X &x, X y) {return (x > y + eps ? x = y, true : false);}
void add(int &x, int y) {x += y; if(x >= MOD) x -= MOD;}
void sub(int &x, int y) {x -= y; if(x < 0) x += MOD;}
int radd(int x, int y) {add(x, y); return x;}
int rsub(int x, int y) {sub(x, y); return x;}
string to2(int val) {bitset<10> temp(val); return temp.to_string();}
int n, k;
int t[N];
namespace SUB1 {
int f[21][21];
int dp(int pos, int cnt) {
if(pos > n) return 0;
if(cnt >= k) return INF;
int &res = f[pos][cnt];
if(res != -1) return res;
res = INF;
Each(int, i, pos, n)
minimize(res, dp(i + 1, cnt + 1) + t[i] + 1 - t[pos]);
return res;
}
void solve() {
memset(f, -1, sizeof f);
cout << dp(1, 0);
exit(0);
}
}
namespace SUB2 {
ll f[5001][5001];
ll dp(int pos, int cnt) {
if(pos > n) return 0;
ll &res = f[pos][cnt];
if(res != -1) return res;
res = dp(pos + 1, cnt) + t[pos] - t[pos - 1];
if(cnt + 1 <= k)
minimize(res, dp(pos + 1, cnt + 1) + 1);
return res;
}
void solve() {
memset(f, -1, sizeof f);
cout << dp(2, 1) + 1;
exit(0);
}
}
namespace SUB3 {
int a[N];
void solve() {
Each(int, i, 1, n - 1)
a[i] = t[i + 1] - t[i];
ll ans = t[n] - t[1] + k;
sort(a + 1, a + n, greater<int>());
Each(int, i, 1, k - 1)
ans -= a[i];
cout << ans;
}
}
int main() {
// #ifndef ONLINE_JUDGE
// freopen("JOI18_stove.inp", "r", stdin);
// freopen("JOI18_stove.out", "w", stdout);
// #endif
ios::sync_with_stdio(false);cin.tie(nullptr);
cin >> n >> k;
Each(int, i, 1, n) cin >> t[i];
if(n <= 20) SUB1::solve();
if(n <= 5000) SUB2::solve();
SUB3::solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
70 ms |
196260 KB |
Output is correct |
11 |
Correct |
81 ms |
196420 KB |
Output is correct |
12 |
Correct |
109 ms |
196220 KB |
Output is correct |
13 |
Correct |
140 ms |
196228 KB |
Output is correct |
14 |
Correct |
161 ms |
196180 KB |
Output is correct |
15 |
Correct |
160 ms |
196244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
70 ms |
196260 KB |
Output is correct |
11 |
Correct |
81 ms |
196420 KB |
Output is correct |
12 |
Correct |
109 ms |
196220 KB |
Output is correct |
13 |
Correct |
140 ms |
196228 KB |
Output is correct |
14 |
Correct |
161 ms |
196180 KB |
Output is correct |
15 |
Correct |
160 ms |
196244 KB |
Output is correct |
16 |
Correct |
16 ms |
1988 KB |
Output is correct |
17 |
Correct |
17 ms |
1988 KB |
Output is correct |
18 |
Correct |
17 ms |
1964 KB |
Output is correct |
19 |
Correct |
19 ms |
2040 KB |
Output is correct |
20 |
Correct |
18 ms |
1988 KB |
Output is correct |
21 |
Correct |
17 ms |
2008 KB |
Output is correct |
22 |
Correct |
16 ms |
1988 KB |
Output is correct |
23 |
Correct |
17 ms |
1988 KB |
Output is correct |
24 |
Correct |
18 ms |
1968 KB |
Output is correct |