#include<bits/stdc++.h>
using namespace std ;
#define maxn 300009
#define ll long long
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define re exit(0);
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
const int mod = 1e9+7 ;
const int INF = 1e9 ;
const int LOG = 18 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
typedef vector<ll> vl ;
typedef pair<ll,ll> pll ;
typedef vector<pll> vll ;
void add ( int &a , int b )
{
a += b ;
if ( a >= 2000 ) a = 2000 ;
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void rf ( )
{
freopen ("bai1.inp","r",stdin) ;
// freopen ("bai1.out","w",stdout) ;
}
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow ( a , n / 2 ) ;
if ( n % 2 ) return ( 1ll * res * res % mod * a % mod ) ;
else return ( 1ll * res * res % mod ) ;
}
int n , k , c ;
int a [maxn][7] ;
int b [maxn][7] , sz [maxn] ;
map <int,int> order ; int num ;
int get_hash ( vi state )
{
int hashA = 0 ;
for ( int i = 0 ; i < k ; i ++ ) hashA = (1ll*hashA*53 + b[state[i]][i]) % mod ;
if ( !order.count (hashA) ) order [hashA] = ++ num ;
return order [hashA] ;
}
ll total_c ;
int dp[2][65][6] ;
int need_value [7] ;
void solve ( vi state )
{
for ( int i = 0 ; i < k ; i ++ ) need_value [i] = b [state[i]][i] ;
memset ( dp , 0 , sizeof dp ) ;
dp [0][0][0] = 1 ;
for ( int i = 0 ; i < n ; i ++ )
{
for ( int mask = 0 ; mask < (1<<k) ; mask ++ )
{
for ( int t = 0 ; t <= k ; t ++ )
{
int T = dp [0][mask][t] ;
int new_mask = mask ;
bool ok = true ;
for ( int r = 0 ; r < k ; r ++ )
{
if ( a [i+1][r] == need_value [r] ) new_mask |= (1<<r) ;
if ( a [i+1][r] > need_value [r] ) ok = false ;
}
if ( t + 1 <= k && ok == true ) add (dp[1][new_mask][t+1],T) ;
add (dp[1][mask][t],T) ;
}
}
for ( int mask = 0 ; mask < (1<<k) ; mask ++ )
{
for ( int t = 0 ; t <= k ; t ++ )
{
dp [0][mask][t] = dp [1][mask][t] ;
dp [1][mask][t] = 0 ;
}
}
}
total_c += dp [0][(1<<k)-1][k] ;
}
bool d [maxn] ;
struct shape {
vi state ;
int sum ;
bool operator < ( const shape &o ) const {
return sum < o.sum ;
}
};
void dijkstra ( )
{
int sum = 0 ;
vi state ;
for ( int j = 0 ; j < k ; j ++ ) state . pb (1) , sum += b [1][j];
priority_queue<shape> S ;
S . push ({state,sum}) ;
d [get_hash(state)] = true ;
while ( !S.empty() )
{
shape t = S.top() ; S.pop() ;
state = t.state ;
solve (state) ;
if ( total_c >= c )
{
cout << t.sum ; re
}
vi new_state ;
for ( int i = 0 ; i < k ; i ++ )
{
if ( state[i] == sz [i] ) continue ;
new_state = state ;
new_state [i] ++ ;
sum = 0 ;
for ( int j = 0 ; j < k ; j ++ ) sum += b [new_state[j]][j] ;
if ( d[get_hash(new_state)] == false )
{
S . push ({new_state,sum}) ;
d [get_hash(new_state)] = true ;
}
}
}
}
int main ( )
{
ios_base :: sync_with_stdio (0) ;
cin.tie(0) ; cout.tie(0) ;
// rf () ;
cin >> n >> k >> c ;
for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 0 ; j < k ; j ++ ) cin >> a [i][j] ;
for ( int j = 0 ; j < k ; j ++ )
{
set <int> S ;
for ( int i = 1 ; i <= n ; i ++ ) S . insert (a[i][j]) ;
vi v ;
for ( auto x : S ) v . pb (x) ;
reverse(v.begin(),v.end()) ;
for ( auto x : v ) b [++sz[j]][j] = x ;
}
dijkstra () ;
}
//-std=c++11
// check special
// range , time , error , stay hard stay hard
// there is no tomorrow
Compilation message
olympiads.cpp: In function 'void rf()':
olympiads.cpp:35:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen ("bai1.inp","r",stdin) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
20 ms |
4440 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
173 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
212 ms |
5068 KB |
Output is correct |
| 4 |
Correct |
260 ms |
5072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
97 ms |
4808 KB |
Output is correct |
| 4 |
Correct |
74 ms |
4552 KB |
Output is correct |
| 5 |
Correct |
84 ms |
4560 KB |
Output is correct |
| 6 |
Correct |
21 ms |
4592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
20 ms |
4440 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
59 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
173 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
212 ms |
5068 KB |
Output is correct |
| 8 |
Correct |
260 ms |
5072 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
97 ms |
4808 KB |
Output is correct |
| 12 |
Correct |
74 ms |
4552 KB |
Output is correct |
| 13 |
Correct |
84 ms |
4560 KB |
Output is correct |
| 14 |
Correct |
21 ms |
4592 KB |
Output is correct |
| 15 |
Execution timed out |
2041 ms |
4928 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
