제출 #198520

#제출 시각아이디문제언어결과실행 시간메모리
198520killB0xStove (JOI18_stove)C++14
0 / 100
5 ms376 KiB
#include <bits/stdc++.h> using namespace std; using namespace std::chrono; typedef long long int ll; typedef unsigned long long int ull; typedef pair<int,int> ii; typedef pair<ll,ll> dl; typedef vector<ii> vii; typedef vector<dl> vdll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<string> vs; #define pb push_back #define mp make_pair #define ft first #define sc second #define in insert #define bs binary_search #define rc(s) return cout << s,0 const ll mod=1e9+7; const int N=100005; #define M_PI 3.14159265358979323846 #define INF LLONG_MAX/2 #define sz(x) ((int)(x.size())) #define int ll #define endl '\n' #define map unordered_map /*----------------------------*/ int dp[5005][5005],a[5005]; /*----------------------------*/ int32_t main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n,k; cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)dp[i][j]=INF; dp[1][1]=a[1]; for(int j=1;j<=k;j++) { for(int i=1;i<=n;i++) { if(i==1)dp[i][j]=a[1]; else dp[i][j]=min(min(dp[i-1][j-1]+1,dp[i-1][j]+a[i]-a[i-1]),dp[i][j-1]); //cout<<dp[i][j]<<" "; } //cout<<endl; } int ans=INF; for(int i=1;i<=k;i++)ans=min(ans,dp[n][i]); rc(ans); //THIS IS IS THE END }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...