oj.uz

답안 #230860

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230860 2020-05-11T22:46:04 Z frodakcin 조교 (CEOI16_popeala) C++11
26 / 100
 2000 ms 6392 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[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<=N;++i)
		q[i].k=i;
	memset(dp, -1, sizeof dp);
	dp[0][0] = 0;
	o[0]=-1;
	for(int i=1;i<=S;++i)
	{
		for(int j=1;j<=T;++j)
		{
			for(int k=0;k<N;++k)
				o[k+1]=pr[k][j];
			std::sort(o+1, o+N+1);
			o[N+1]=j-1;//			CHECK (J-1) IS CORRECT?
			for(int k=0;k<=N;++k)
			{
				//printf("\tRANGE (%d): (%d, %d]\n", k, o[k], o[k+1]);
				if(q[k].chk(o[k], o[k+1]))
					rpl(dp[1][j], q[k].get() + k*p[j]);//(]
			}
			//printf("dp[%d][%d] = %d\n", i, j, dp[1][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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 1280 KB Output is correct
2 Correct 54 ms 1280 KB Output is correct
3 Correct 60 ms 1280 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 250 ms 1912 KB Output is correct
2 Correct 359 ms 1792 KB Output is correct
3 Correct 427 ms 2136 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 63 ms 1280 KB Output is correct
4 Correct 54 ms 1280 KB Output is correct
5 Correct 60 ms 1280 KB Output is correct
6 Correct 250 ms 1912 KB Output is correct
7 Correct 359 ms 1792 KB Output is correct
8 Correct 427 ms 2136 KB Output is correct
9 Correct 536 ms 2936 KB Output is correct
10 Correct 895 ms 3444 KB Output is correct
11 Correct 1399 ms 6136 KB Output is correct
12 Correct 1472 ms 6352 KB Output is correct
13 Execution timed out 2100 ms 6392 KB Time limit exceeded
14 Halted 0 ms 0 KB -