| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 790137 |
2023-07-22T11:00:39 Z |
n3rm1n |
Stove (JOI18_stove) |
C++17 |
|
1000 ms |
1492 KB |
/// note: it's actually stove
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e5 + 10;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int n, k, a[MAXN];
void read()
{
cin >> n >> k;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
}
vector < int > before(MAXN), dp(MAXN);
int inf = 1e9+10;
int best, best_opt, cost, cut;
void divide(int l, int r, int opt_left, int opt_right)
{
if(l > r)return;
int mid = (l + r)/2;
dp[mid] = inf;
best = inf;
best_opt = -1;
for (cut = opt_left; cut <= min(mid, opt_right); ++ cut)
{
cost = before[cut-1] + a[mid] - a[cut] + 1;
if(cost < best)
{
best = cost;
best_opt = cut;
}
}
dp[mid] = best;
divide(l, mid-1, opt_left, best_opt);
divide(mid+1, r, best_opt, opt_right);
}
void solve()
{
dp[0] = 0;
for (int i = 1; i <= n; ++ i)
dp[i] = inf;
for (int i = 1; i <= k; ++ i)
{
before = dp;
divide(1, n, 1, n);
}
cout << dp[n] << endl;
}
int main()
{
speed();
read();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 12 |
Correct |
78 ms |
1112 KB |
Output is correct |
| 13 |
Correct |
132 ms |
1108 KB |
Output is correct |
| 14 |
Correct |
187 ms |
1120 KB |
Output is correct |
| 15 |
Correct |
184 ms |
1132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 12 |
Correct |
78 ms |
1112 KB |
Output is correct |
| 13 |
Correct |
132 ms |
1108 KB |
Output is correct |
| 14 |
Correct |
187 ms |
1120 KB |
Output is correct |
| 15 |
Correct |
184 ms |
1132 KB |
Output is correct |
| 16 |
Correct |
29 ms |
1492 KB |
Output is correct |
| 17 |
Correct |
199 ms |
1492 KB |
Output is correct |
| 18 |
Execution timed out |
1078 ms |
1492 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
