Submission #46431612
Source Code Expand
/*
Author : Hocky Yudhiono
Sel 10 Okt 2023 05:30:14
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<ll, ll> PLL;
typedef pair<ll, ll> pll;
typedef long double ld;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define popf pop_front
#define pf push_front
#define popb pop_back
#define pb push_back
#define fi first
#define se second
const double EPS = 1e-9;
const int INFMEM = 63;
// Do dir^1 to get reverse direction
const int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
const char dch[4] = {'R', 'L', 'D', 'U'};
// Do (dir + 2)%4 to get reverse direction
// const int dx[8] = {-1,0,1,0,-1,1,1,-1};
// const int dy[8] = {0,1,0,-1,1,1,-1,-1};
// const char dch[4] = {'U','R','D','L'};
const double PI = 3.141592653589793;
inline void fasterios() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
}
#define endl '\n'
const int MOD = 1000000007;
// const int MOD = 998244353;
LL n, k, p;
LL memo[2][10005];
vector <vector<LL>> states;
vector <LL> encode;
vector <LL> currentState;
LL getState(const vector <LL> &decodedState) {
LL sum = 0;
trav(tmp, decodedState) {
sum *= 6;
sum += tmp;
}
return sum;
}
void fillStates(LL pos) {
if (pos == k) {
states.pb(currentState);
encode.pb(getState(currentState));
return;
}
for (int i = 0; i <= p; i++) {
currentState[pos] = i;
fillStates(pos + 1);
}
}
int main() {
fasterios();
cin >> n >> k >> p;
for (int i = 0; i <= 10000; i++) memo[0][i] = LLONG_MAX;
memo[0][0] = 0;
currentState.resize(k);
fillStates(0);
for (int i = 1; i <= n; i++) {
LL cost; cin >> cost;
vector <int> addParam(k);
trav(cur, addParam) cin >> cur;
int asu = i & 1;
for (int j = 0; j <= 10000; j++) memo[asu][j] = memo[!asu][j];
rep(stateIter, 0, sz(encode)) {
if (memo[!asu][encode[stateIter]] == LLONG_MAX) continue;
auto nextState = states[stateIter];
rep(j, 0, k) {
nextState[j] += addParam[j];
nextState[j] = min(nextState[j], p);
}
auto encodedState = getState(nextState);
memo[asu][encodedState] = min(memo[asu][encodedState], memo[!asu][encode[stateIter]] + cost);
}
}
if (memo[n & 1][encode.back()] == LLONG_MAX) memo[n & 1][encode.back()] = -1;
cout << memo[n & 1][encode.back()] << endl;
}
Submission Info
Submission Time |
|
Task |
E - Product Development |
User |
hocky |
Language |
C++ 20 (gcc 12.2) |
Score |
475 |
Code Size |
2739 Byte |
Status |
AC |
Exec Time |
14 ms |
Memory |
4128 KiB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
475 / 475 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example_00.txt, example_01.txt |
All |
example_00.txt, example_01.txt, test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt |
Case Name |
Status |
Exec Time |
Memory |
example_00.txt |
AC |
1 ms |
3660 KiB |
example_01.txt |
AC |
1 ms |
3632 KiB |
test_00.txt |
AC |
1 ms |
3648 KiB |
test_01.txt |
AC |
1 ms |
3668 KiB |
test_02.txt |
AC |
4 ms |
4060 KiB |
test_03.txt |
AC |
1 ms |
3588 KiB |
test_04.txt |
AC |
1 ms |
3764 KiB |
test_05.txt |
AC |
1 ms |
3740 KiB |
test_06.txt |
AC |
1 ms |
3644 KiB |
test_07.txt |
AC |
5 ms |
4080 KiB |
test_08.txt |
AC |
2 ms |
4080 KiB |
test_09.txt |
AC |
2 ms |
4012 KiB |
test_10.txt |
AC |
5 ms |
4008 KiB |
test_11.txt |
AC |
12 ms |
4080 KiB |
test_12.txt |
AC |
9 ms |
4016 KiB |
test_13.txt |
AC |
8 ms |
4060 KiB |
test_14.txt |
AC |
1 ms |
3808 KiB |
test_15.txt |
AC |
1 ms |
3648 KiB |
test_16.txt |
AC |
1 ms |
3640 KiB |
test_17.txt |
AC |
1 ms |
3572 KiB |
test_18.txt |
AC |
1 ms |
3576 KiB |
test_19.txt |
AC |
1 ms |
3764 KiB |
test_20.txt |
AC |
1 ms |
3664 KiB |
test_21.txt |
AC |
1 ms |
4124 KiB |
test_22.txt |
AC |
1 ms |
3640 KiB |
test_23.txt |
AC |
3 ms |
3956 KiB |
test_24.txt |
AC |
2 ms |
4072 KiB |
test_25.txt |
AC |
2 ms |
4080 KiB |
test_26.txt |
AC |
3 ms |
4080 KiB |
test_27.txt |
AC |
2 ms |
4076 KiB |
test_28.txt |
AC |
2 ms |
4016 KiB |
test_29.txt |
AC |
3 ms |
4080 KiB |
test_30.txt |
AC |
5 ms |
4008 KiB |
test_31.txt |
AC |
5 ms |
4080 KiB |
test_32.txt |
AC |
4 ms |
4076 KiB |
test_33.txt |
AC |
5 ms |
4048 KiB |
test_34.txt |
AC |
4 ms |
4016 KiB |
test_35.txt |
AC |
5 ms |
4076 KiB |
test_36.txt |
AC |
5 ms |
4016 KiB |
test_37.txt |
AC |
13 ms |
4080 KiB |
test_38.txt |
AC |
13 ms |
4128 KiB |
test_39.txt |
AC |
13 ms |
4080 KiB |
test_40.txt |
AC |
13 ms |
3996 KiB |
test_41.txt |
AC |
14 ms |
4076 KiB |
test_42.txt |
AC |
13 ms |
4016 KiB |
test_43.txt |
AC |
12 ms |
4080 KiB |