답안 #604381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
604381 2022-07-25T05:16:19 Z SeDunion 조교 (CEOI16_popeala) C++17
17 / 100
2000 ms 47948 KB
#include<iostream>

using namespace std;
//using ll = long long;

#define ll int

const ll inf = 1e9 + 123;

const int T = 4e3 + 123;
const int N = 52;
const int S = 52;

ll pref[T];
int cs[N][T];
ll val[T][T];
ll dp[T][S];

void upd(ll &a, ll b) {
	a = min(a, b);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, t, s;
	cin >> n >> t >> s;
	for (int i = 1 ; i <= t ; ++ i) {
		cin >> pref[i];
		pref[i] += pref[i - 1];
	}
	for (int i = 1 ; i <= n ; ++ i) {
		for (int j = 1 ; j <= t ; ++ j) {
			char c; cin >> c;
			cs[i][j] = cs[i][j - 1] + (c == '1');
		}
	}
	for (int l = 0 ; l <= t ; ++ l) {
		for (int r = l + 1 ; r <= t ; ++ r) {
			int cnt = 0;
			for (int i = 1 ; i <= n ; ++ i) {
				cnt += (cs[i][r] - cs[i][l] == r - l);
			}
			val[l][r] = cnt * (pref[r] - pref[l]);
		}
	}
	for (int i = 0 ; i <= t ; ++ i) {
		for (int x = 0 ; x <= s ; ++ x) {
			dp[i][x] = inf;
		}
	}
	dp[0][0] = 0;
	for (int i = 1 ; i <= t ; ++ i) {
		for (int x = 1 ; x <= s ; ++ x) {
			for (int j = 0 ; j < i ; ++ j) {
				upd(dp[i][x], dp[j][x-1] + val[j][i]);
			}
		}
	}
	for (int i = 1 ; i <= s ; ++ i) {
		cout << dp[t][i] << "\n";
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 3284 KB Output is correct
2 Correct 16 ms 3244 KB Output is correct
3 Correct 16 ms 3208 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 735 ms 19696 KB Output is correct
2 Correct 1750 ms 31488 KB Output is correct
3 Execution timed out 2080 ms 47948 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 19 ms 3284 KB Output is correct
4 Correct 16 ms 3244 KB Output is correct
5 Correct 16 ms 3208 KB Output is correct
6 Correct 735 ms 19696 KB Output is correct
7 Correct 1750 ms 31488 KB Output is correct
8 Execution timed out 2080 ms 47948 KB Time limit exceeded
9 Halted 0 ms 0 KB -