| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171881 |
2019-12-30T14:51:04 Z |
Swan |
UFO (IZhO14_ufo) |
C++14 |
|
2000 ms |
16960 KB |
#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
//#define int long long
using namespace std;
const int maxn = 100004;
vector<int> v;
int dp[102][maxn];
int f[102][maxn];
int tree[102][4*maxn];
int fst_mx[maxn];
void build(int num,int v,int l,int r){
if(l == r && num == 1){
tree[num][v] = dp[num][l];
return;
}
if(l == r){
tree[num][v] = 1e9;
return;
}
int m = (l+r)/2;
build(num,v*2,l,m);
build(num,v*2+1,m+1,r);
tree[num][v] = min(tree[num][v*2],tree[num][v*2+1]);
}
int get_min(int num,int v,int l,int r,int le,int re){
if(l>=le && r <=re)return tree[num][v];
if(l > re || r < le)return 1e9;
int m = (l+r)/2;
int a = get_min(num,v*2,l,m,le,re);
int b = get_min(num,v*2+1,m+1,r,le,re);
return min(a,b);
}
void set_pos(int num,int v,int l,int r,int need){
if(l == r){
tree[num][v] = dp[num][l];
return;
}
int m = (l+r)/2;
if(need<=m)set_pos(num,v*2,l,m,need);
else set_pos(num,v*2+1,m+1,r,need);
tree[num][v] = min(tree[num][v*2],tree[num][v*2+1]);
}
int n,k;
void brute(){
for(int cnt(2);cnt<=k;cnt++){
for(int i(cnt);i<=n;i++){
f[cnt][i] = 1e9;
int now = v[i];
for(int to(i-1);to>=0;to--){
f[cnt][i] = min(f[cnt][i],now+f[cnt-1][to]);
}
}
}
cout << f[k][n] << endl;
}
main(){
ios_base::sync_with_stdio(0);
cin >> n >> k;
v.push_back(0);
int now = 0;
dp[1][0] = f[1][0] = 1e9;
for(int i(1); i <= n;i++){
int x; cin >> x;
now = max(now,x);
f[1][i] = dp[1][i] = now;
v.push_back(x);
fst_mx[i] = -1;
}
stack<int> s;
for(int i(0); i < n;i++){
while(s.size() && (v[s.top()] < v[i]))s.pop();
if(s.size())fst_mx[i] = s.top();
s.push(i);
}
for(int i(1);i<=k;i++)build(i,1,0,n);
//cout << get_min(2,1,0,n,0,3) << endl;
for(int cnt(2);cnt<=k;cnt++){
for(int i(cnt);i<=n;i++){
int now = 1e9;
if(dp[cnt-1][i-1]!=1e9){
now = dp[cnt-1][i-1]+v[i];
}
int nxt = fst_mx[i];
int to = 0;
//cout << now << endl;
if(nxt!=-1){
now = min(now,dp[cnt][nxt]);
to = nxt+1;
}
//cout << now << endl;
if(to!=i)now = min(now,v[i]+get_min(cnt-1,1,0,n,to,i-1));
//cout << i << ' ' << v[i] << ' ' << to << ' ' << i-1 << ' ' << get_min(cnt-1,1,0,n,to,i-1) << endl;
dp[cnt][i] = now;
//cout << cnt << ' ' << i << ' ' << now << ' ' << to << ' ' << i << endl;
set_pos(cnt,1,0,n,i);
}
}
brute();
return 0;
}
/*
5 4
1 2 3 4 5
*/
Compilation message
ufo.cpp:68:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
1272 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
2168 KB |
Output isn't correct |
| 5 |
Runtime error |
19 ms |
2424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
23 ms |
4860 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
20 ms |
2424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
19 ms |
2296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
19 ms |
2424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
20 ms |
2396 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
19 ms |
2296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
19 ms |
2300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Execution timed out |
2039 ms |
16688 KB |
Time limit exceeded |
| 14 |
Runtime error |
19 ms |
2424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
19 ms |
2296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
19 ms |
2424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Execution timed out |
2057 ms |
16960 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2058 ms |
12816 KB |
Time limit exceeded |
| 19 |
Runtime error |
18 ms |
2424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
19 ms |
2424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
