Submission #46111502

---

Source Code Expand

#include<bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
using ll=long long;

/////////////////////////////////////////////////////////////////////////
// chmax, chmin
/////////////////////////////////////////////////////////////////////////
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

/////////////////////////////////////////////////////////////////////////
// constants
/////////////////////////////////////////////////////////////////////////
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

/////////////////////////////////////////////////////////////////////////
// I/O
/////////////////////////////////////////////////////////////////////////
struct IOSetup{
	IOSetup(){
		cin.tie(0);
		ios::sync_with_stdio(0);
		cout<<fixed<<setprecision(12);
	}
} iosetup;

/////////////////////////////////////////////////////////////////////////
// vector
/////////////////////////////////////////////////////////////////////////
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
	for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
	return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
	for(T &x:v)is>>x;
	return is;
}

/////////////////////////////////////////////////////////////////////////
// debug
/////////////////////////////////////////////////////////////////////////
namespace myDebug
{
bool DEBUG_FLAG = true;

template<class Last>
void DEBUG(Last &&last)
{
	if (DEBUG_FLAG)
		cerr << last << endl;
}

template <class Head, class... Tail>
void DEBUG(Head &&head, Tail&&... tail)
{
	if (DEBUG_FLAG)
		cerr << head << ", ";
	DEBUG(forward<Tail>(tail)...);
}
}
using myDebug::DEBUG;

/////////////////////////////////////////////////////////////////////////
// Libraries from https://github.com/mugen1337/procon
/////////////////////////////////////////////////////////////////////////


/////////////////////////////////////////////////////////////////////////
// solve 
/////////////////////////////////////////////////////////////////////////

int main()
{
	int N, K, P; cin >> N >> K >> P;
	vector<ll> C(N);
	vector<vector<ll>> A(N, vector<ll>(5, P));
	rep(i, N)
	{
		cin >> C[i];
		rep(j, K)
			cin >> A[i][j];
	}

	const int M = 7776;

	using State = tuple<int, int, int, int, int>;
	auto get = [](State s)
	{
		int a, b, c, d, e;
		tie(a, b, c, d, e) = s;
		int ret = 0;
		ret = a;
		ret = ret * 6 + b;
		ret = ret * 6 + c;
		ret = ret * 6 + d;
		ret = ret * 6 + e;
		return ret;
	};
	auto teg = [](int idx)
	{
		int a, b, c, d, e;
		e = idx % 6;
		idx /= 6;
		d = idx % 6;
		idx /= 6;
		c = idx % 6;
		idx /= 6;
		b = idx % 6;
		idx /= 6;
		a = idx % 6;
		return make_tuple(a, b, c, d, e);
	};

	const ll linf = 100000000001000;
	vector<vector<ll>> dp(N + 1, vector<ll>(M, linf));
	dp[0][0] = 0;

	auto add = [&P](int a, int b)
	{
		return min(a + b, P);
	};
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			chmin(dp[i + 1][j], dp[i][j]);

			auto [a, b, c, d, e] = teg(j);
			a = add(a, A[i][0]);
			b = add(b, A[i][1]);
			c = add(c, A[i][2]);
			d = add(d, A[i][3]);
			e = add(e, A[i][4]);
			auto idx = get(make_tuple(a, b, c, d, e));
			chmin(dp[i + 1][idx], dp[i][j] + C[i]);
		}
	}
	

	int ok = get(make_tuple(P, P, P, P, P));
	cout << (dp[N][ok] >= linf ? -1ll : dp[N][ok]) << endl;
	return 0;
}

Submission Info

Judge Result