oj.uz

Submission #230867

# Submission time Handle Problem Language Result Execution time Memory
230867 2020-05-11T22:51:34 Z frodakcin Popeala (CEOI16_popeala) C++11
100 / 100
 895 ms 10616 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 896 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1408 KB Output is correct
2 Correct 27 ms 1408 KB Output is correct
3 Correct 28 ms 1408 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 2176 KB Output is correct
2 Correct 148 ms 2432 KB Output is correct
3 Correct 178 ms 2864 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 31 ms 1408 KB Output is correct
4 Correct 27 ms 1408 KB Output is correct
5 Correct 28 ms 1408 KB Output is correct
6 Correct 105 ms 2176 KB Output is correct
7 Correct 148 ms 2432 KB Output is correct
8 Correct 178 ms 2864 KB Output is correct
9 Correct 249 ms 3968 KB Output is correct
10 Correct 418 ms 4848 KB Output is correct
11 Correct 706 ms 9208 KB Output is correct
12 Correct 725 ms 9592 KB Output is correct
13 Correct 837 ms 9592 KB Output is correct
14 Correct 895 ms 10616 KB Output is correct
15 Correct 868 ms 10488 KB Output is correct