oj.uz

답안 #134111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134111 2019-07-22T05:45:00 Z 임유진(#3231) 조교 (CEOI16_popeala) C++14
17 / 100
 2000 ms 31152 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1 << 30;
const int MAXN = 55;
const int MAXT  = 4005;

int P[MAXT];
char R[MAXN][MAXT];
int sp[MAXT], cnt[MAXT][MAXT];
bool cor[MAXN];
int dp[MAXN][MAXT];

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int N, T, S;

	cin >> N >> T >> S;
	for(int i = 1; i <= T; i++) cin >> P[i];
	for(int i = 0; i < N; i++) cin >> R[i];

	for(int i = 1; i <= T; i++) sp[i] = sp[i - 1] + P[i];
	for(int i = 1; i <= T; i++) {
		for(int j = 0; j < N; j++) cor[j] = true;
		cnt[i][i - 1] = N;
		for(int j = i; j <= T; j++) {
			cnt[i][j] = cnt[i][j - 1];
			for(int k = 0; k < N; k++) if(cor[k] && R[k][j - 1] == '0') {
				cnt[i][j]--;
				cor[k] = false;
			}
			//printf("cnt[%d][%d] = %d\n", i, j, cnt[i][j]);
		}
	}
	//for(int i = 0; i <= T; i++) printf("%d ", sp[i]);
	//printf("\n");
	for(int i = 1; i <= S; i++) dp[i][0] = INF;
	for(int i = 1; i <= T; i++) dp[0][i] = INF;
	for(int i = 1; i <= S; i++) for(int j = 1; j <= T; j++) {
		dp[i][j] = INF;
		for(int k = j; k > 0; k--) 
			dp[i][j] = min(dp[i][j], dp[i - 1][k - 1] + (sp[j] - sp[k - 1]) * cnt[k][j]);
		//printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
	}

	for(int i = 1; i <= S; i++) cout << dp[i][T] << "\n";
	return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 760 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 3448 KB Output is correct
2 Correct 33 ms 3448 KB Output is correct
3 Correct 31 ms 3448 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1082 ms 19652 KB Output is correct
2 Execution timed out 2036 ms 31152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 32 ms 3448 KB Output is correct
4 Correct 33 ms 3448 KB Output is correct
5 Correct 31 ms 3448 KB Output is correct
6 Correct 1082 ms 19652 KB Output is correct
7 Execution timed out 2036 ms 31152 KB Time limit exceeded
8 Halted 0 ms 0 KB -