Submission #1989261
Source Code Expand
#include <bits/stdc++.h>
//#include <math.h>
using namespace std;
#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> PP;
//-----------------------------------------------------------------------------
int n,k;
ll a[15],mi=LINF;
void dfs(int idx,ll ma,ll sum,int num) {
//cout<<idx<<' '<<ma<<' '<<sum<<' '<<num<<endl;
if(idx==n) {
if(num>=k) mi=min(mi,sum);
return;
}
dfs(idx+1,max(ma,a[idx]),sum,num);
if(ma<a[idx]) dfs(idx+1,a[idx],sum,num+1);
else {
ll cost=ma-a[idx]+1;
dfs(idx+1,ma+1,sum+cost,num+1);
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n>>k;
REP(i,n) cin>>a[i];
dfs(0,0,0,0);
cout<<mi<<endl;
return 0;
}
Submission Info
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
120 / 120 |
90 / 90 |
140 / 140 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sub0_in1.txt, sub0_in2.txt |
Subtask1 |
sub1_in1.txt, sub1_in2.txt |
Subtask2 |
sub2_in1.txt, sub2_in2.txt, sub2_in3.txt |
Subtask3 |
sub0_in1.txt, sub0_in2.txt, sub1_in1.txt, sub1_in2.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt |
Case Name |
Status |
Exec Time |
Memory |
sub0_in1.txt |
AC |
1 ms |
256 KB |
sub0_in2.txt |
AC |
1 ms |
256 KB |
sub1_in1.txt |
AC |
1 ms |
256 KB |
sub1_in2.txt |
AC |
1 ms |
256 KB |
sub2_in1.txt |
AC |
1 ms |
256 KB |
sub2_in2.txt |
AC |
1 ms |
256 KB |
sub2_in3.txt |
AC |
1 ms |
256 KB |
sub3_in1.txt |
AC |
1 ms |
256 KB |
sub3_in2.txt |
AC |
1 ms |
256 KB |