Submission #230867

#	Time	Username	Problem	Language	Result	Execution time	Memory
230867		frodakcin	Popeala (CEOI16_popeala)	C++11	100 / 100	895 ms	10616 KiB

popeala

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>

/*

	 Can we use dp[T] (1-dimensional) for each S-layer, and sweep for N?
	 */

template<typename T> bool ckmax(T& a, T b){return a<b?a=b,1:0;}
template<typename T> bool ckmin(T& a, T b){return a>b?a=b,1:0;}
int rpl(int& a, int b){return !~a||b<a?a=b,1:0;}

const int MT=1<<15;
const int MN=52, MS=52;
const int INF=2e9+10;
int T, N, S, a[MT], p[MT], pr[MN][MT], dp[2][MT], o[MT][MN];
bool b[MN][MT];
char s[MN];

struct val{public: int i, v;};
struct dque : public std::deque<val>
{
public:
	int k, r;
	bool chk(int nl, int nr)
	{
		for(;r <= nr;++r)
		{
			if(!~dp[0][r])
				continue;
			val x = {r, dp[0][r]-p[r]*k};
			for(;!empty() && x.v <= back().v;)
				pop_back();
			push_back(x);
		}
		for(;!empty() && front().i <= nl;)
			pop_front();
		return !empty();
	}
	int get() {return front().v;}
} q[MN];

int main(void)
{
	scanf("%d%d%d", &N, &T, &S);
	for(int i=0;i<T;++i)
		scanf("%d", a+i), p[i+1]=p[i]+a[i];
	for(int i=0;i<N;++i)
	{
		scanf(" %s", s);
		pr[i][0] = -1;
		for(int j=0;j<T;++j)
		{
			b[i][s[j]]=s[j]=='0';
			pr[i][j+1] = s[j]=='0'?j:pr[i][j];//prev occurence in [0, j)
		}
	}
	for(int i=0;i<=T;++i)
	{
		o[i][0]=-1, o[i][N+1]=i-1;
		for(int j=0;j<N;++j)
			o[i][j+1]=pr[j][i];
		std::sort(o[i]+1, o[i]+N+1);
	}
	for(int i=0;i<=N;++i)
		q[i].k=i;
	memset(dp, -1, sizeof dp);
	dp[0][0] = 0;
	for(int i=1;i<=S;++i)
	{
		for(int j=1;j<=T;++j)
			for(int k=0;k<=N;++k)
				if(q[k].chk(o[j][k], o[j][k+1]))
					rpl(dp[1][j], q[k].get() + k*p[j]);//(]
		printf("%d\n", dp[1][T]);

		memcpy(dp[0], dp[1], sizeof dp[1]);
		memset(dp[1], -1, sizeof dp[1]);
		for(int j=0;j<=N;++j)
			q[j].clear(), q[j].r=0;
	}
	return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:57:13: warning: array subscript has type 'char' [-Wchar-subscripts]
    b[i][s[j]]=s[j]=='0';
             ^
popeala.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &T, &S);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:50:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i), p[i+1]=p[i]+a[i];
   ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
popeala.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", s);
   ~~~~~^~~~~~~~~~

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