oj.uz

Submission #787262

# Submission time Handle Problem Language Result Execution time Memory
787262 2023-07-19T01:04:36 Z YassirSalama Stove (JOI18_stove) C++14
50 / 100
 298 ms 262144 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#define dbg(x) cout << "[ " << #x << " ] : " << x<<endl;
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=5500;
int dp[MAXN][MAXN];//[i,k]
vector<int> v(MAXN,0);
int n,k;
vector<int> ds(MAXN,0);
const int INF=1e18;
int solve(int i,int kk){
	if(kk<0) return INF;
	if(i>=n-1) return 0;
	if(dp[i][kk]!=-1) return dp[i][kk];
	return dp[i][kk]=min(
			solve(i+1,kk-1),
			solve(i+1,kk)+ds[i]
		);
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n>>k;
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++) cin>>v[i];
for(int i=0;i<n;i++) ds[i]=v[i+1]-v[i]-1;
cout<<n+solve(0,k-1)<<endl;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 237068 KB Output is correct
2 Correct 87 ms 237156 KB Output is correct
3 Correct 76 ms 237076 KB Output is correct
4 Correct 75 ms 237128 KB Output is correct
5 Correct 75 ms 237088 KB Output is correct
6 Correct 75 ms 237056 KB Output is correct
7 Correct 83 ms 237192 KB Output is correct
8 Correct 76 ms 237096 KB Output is correct
9 Correct 88 ms 237168 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 237068 KB Output is correct
2 Correct 87 ms 237156 KB Output is correct
3 Correct 76 ms 237076 KB Output is correct
4 Correct 75 ms 237128 KB Output is correct
5 Correct 75 ms 237088 KB Output is correct
6 Correct 75 ms 237056 KB Output is correct
7 Correct 83 ms 237192 KB Output is correct
8 Correct 76 ms 237096 KB Output is correct
9 Correct 88 ms 237168 KB Output is correct
10 Correct 75 ms 237260 KB Output is correct
11 Correct 78 ms 237232 KB Output is correct
12 Correct 98 ms 237228 KB Output is correct
13 Correct 121 ms 237340 KB Output is correct
14 Correct 136 ms 237344 KB Output is correct
15 Correct 138 ms 237308 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 237068 KB Output is correct
2 Correct 87 ms 237156 KB Output is correct
3 Correct 76 ms 237076 KB Output is correct
4 Correct 75 ms 237128 KB Output is correct
5 Correct 75 ms 237088 KB Output is correct
6 Correct 75 ms 237056 KB Output is correct
7 Correct 83 ms 237192 KB Output is correct
8 Correct 76 ms 237096 KB Output is correct
9 Correct 88 ms 237168 KB Output is correct
10 Correct 75 ms 237260 KB Output is correct
11 Correct 78 ms 237232 KB Output is correct
12 Correct 98 ms 237228 KB Output is correct
13 Correct 121 ms 237340 KB Output is correct
14 Correct 136 ms 237344 KB Output is correct
15 Correct 138 ms 237308 KB Output is correct
16 Runtime error 298 ms 262144 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -