oj.uz

Submission #134110

# Submission time Handle Problem Language Result Execution time Memory
134110 2019-07-22T05:43:57 Z 임유진(#3231) Popeala (CEOI16_popeala) C++14
8 / 100
 150 ms 1004 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[MAXN][MAXN];
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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 150 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Incorrect 27 ms 888 KB Output isn't correct
4 Halted 0 ms 0 KB -