Submission #1213097

---

Source Code Expand

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>

auto& in = std::cin;
auto& out = std::cout;

template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}

constexpr int64_t INF = 9223372036854775807/10;
int32_t N;
int64_t a[555];
int64_t dp[15][15][1 << 15];
int64_t func(int32_t i, int32_t need, int32_t mask, int64_t max) {
	if (need <= 0) { return 0; }
	if (i >= N) { return INF; }
	auto& memo = dp[i][need][mask];
	if (memo !=-1) {
		return memo;
	}
	return memo= std::min(func(i + 1, need, mask, max),
		func(i + 1, need - 1, mask|(1<<i), std::max(max + 1, a[i])) + std::max<int64_t>(0, max + 1 - a[i])
		);
}
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	fill_all<int64_t>(dp, -1);
	int need;
	in >> N>>need;
	for (int32_t i = 0; i < N; ++i)
	{
		in >> a[i];
	}
	out << func(0, need, 0, 0) << endl;

	return 0;
}
#endif

#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>

auto& in = std::cin;
auto& out = std::cout;

int32_t N;
std::string S[10000];
std::string T;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);

	in >> N;
	for (int32_t i = 0; i < N; ++i)
	{
		in >> S[i];
	}
	in >> T;



	return 0;
}
#endif

Submission Info

Judge Result