Submission #416680

#	Time	Username	Problem	Language	Result	Execution time	Memory
416680		CaroLinda	Popeala (CEOI16_popeala)	C++14	0 / 100	62 ms	2632 KiB

popeala

#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])-1 ; j >= 0 ; j-- )
		{
			int finalSubtask = vec[i][j].first ;

			if( finalSubtask+1 <= i && (j == sz(vec[i])-1 || vec[i][j+1].first != finalSubtask+1) )
				tryImprove( i , finalSubtask+1, tot ) ;

			tot -= vec[i][j].second ;
			tryImprove(i, finalSubtask, 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() ) ;

		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 (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d %d %d", &N, &T , &S ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%lld", &sv[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~
popeala.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |    scanf(" %c", &c ) ;
      |    ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74