#include <bits/stdc++.h>
#define debug printf
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define mk make_pair
const int MAXN = 55 ;
const int MAXT = 2e4+10 ;
const ll inf = 1e17+10LL ;
using namespace std ;
int N , T , S , toGet, toFill = 1 ;
int tab[MAXN][MAXT] ;
int firstZero[MAXN] ;
int freq[MAXT] ;
ll sv[MAXT] ;
ll dp[2][MAXT] ;
vector< pair<int,int> > vec[MAXT] ;
ll getCost(int l, int r ) { return sv[r]-sv[l-1] ; }
void tryImprove( int r , int l, ll qtdOn )
{
if( l == 0 ) return ;
ll val = dp[toGet][l-1] + qtdOn*getCost(l,r) ;
dp[toFill][r] = min( dp[toFill][r] , val ) ;
}
void solve()
{
for(int i = 1 ; i <= T ; i++ )
{
ll tot = N ;
dp[toFill][i] = inf ;
for(int j = sz(vec[i])-2 ; j >= 0 ; j-- )
{
for(int g = vec[i][j].first+1 ; g <= vec[i][j+1].first ; g++ )
tryImprove(i, g, tot) ;
tot -= vec[i][j].second ;
}
for(int g = 1 ; g <= vec[i][0].first ; g++ ) tryImprove(i,g,tot) ;
}
}
int main()
{
scanf("%d %d %d", &N, &T , &S ) ;
for(int i = 1 ; i <= T ; i++ )
{
scanf("%lld", &sv[i] ) ;
sv[i] += sv[i-1] ;
}
char c ;
for(int i = 1 ; i <= N ; i++ )
for(int j = 1 ; j<= T ; j++ )
{
scanf(" %c", &c ) ;
tab[i][j] = (c == '1') ;
}
for(int i = 1 ; i <= T ; i++ )
{
for(int j = 1 ; j<= N ; j++ )
if( !tab[j][i] ) firstZero[j] = i ;
for(int j = 1 ; j <= N ; j++ ) freq[ firstZero[j] ]++ ;
for(int j = 1 ; j <= N ; j++ ) vec[i].push_back( make_pair( firstZero[j] , freq[ firstZero[j] ] ) ) ;
sort(all(vec[i] ) ) ;
vec[i].erase( unique(all(vec[i] ) ) , vec[i].end() ) ;
vec[i].push_back( make_pair(i,0) ) ;
for(auto e : vec[i] ) freq[e.first] = 0 ;
/*debug("Sobre os numeros em %d: ", i ) ;
for(auto e : vec[i] ) debug(" (%d, %d) ", e.first, e.second ) ;
debug("\n") ; */
}
//Base da dp
for(int i = 1 ; i <= T ; i++ )
{
ll qtdOn = (vec[i][0].first == 0 ) ? vec[i][0].second : 0 ;
dp[0][i] = getCost(1,i)*qtdOn ;
}
dp[1][0] = dp[0][0] = inf ;
printf("%lld\n", dp[0][T] ) ;
/*debug("Printing base dp\n") ;
for(int i = 1 ; i <= T ; i++ ) debug("%lld ", dp[0][i] ) ;
debug("\n") ; */
for(int i = 2 ; i <= S ; i++ , swap(toGet, toFill) )
{
solve() ;
printf("%lld\n", dp[toFill][T] ) ;
}
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d %d %d", &N, &T , &S ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%lld", &sv[i] ) ;
| ~~~~~^~~~~~~~~~~~~~~~~
popeala.cpp:71:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf(" %c", &c ) ;
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
716 KB |
Output is correct |
| 2 |
Correct |
1 ms |
844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
1356 KB |
Output is correct |
| 2 |
Correct |
44 ms |
1360 KB |
Output is correct |
| 3 |
Correct |
44 ms |
1384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
673 ms |
2708 KB |
Output is correct |
| 2 |
Correct |
1233 ms |
3396 KB |
Output is correct |
| 3 |
Execution timed out |
2094 ms |
4136 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
716 KB |
Output is correct |
| 2 |
Correct |
1 ms |
844 KB |
Output is correct |
| 3 |
Correct |
45 ms |
1356 KB |
Output is correct |
| 4 |
Correct |
44 ms |
1360 KB |
Output is correct |
| 5 |
Correct |
44 ms |
1384 KB |
Output is correct |
| 6 |
Correct |
673 ms |
2708 KB |
Output is correct |
| 7 |
Correct |
1233 ms |
3396 KB |
Output is correct |
| 8 |
Execution timed out |
2094 ms |
4136 KB |
Time limit exceeded |
