oj.uz

Submission #604397

# Submission time Handle Problem Language Result Execution time Memory
604397 2022-07-25T05:40:44 Z SeDunion Popeala (CEOI16_popeala) C++17
0 / 100
 20 ms 5128 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using ll = long long;

const ll inf = 1e18;

const int T = 1e3 + 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 l0[N][T];
int l1[N][T];

vector<int>v[T];

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) {
		int p0 = 0;
		int p1 = 0;
		for (int j = 1 ; j <= t ; ++ j) {
			char c; cin >> c;
			if (c == '0') p0 = j;
			if (c == '1') p1 = j;
			l0[i][j] = p0;
			l1[i][j] = p1;
			cs[i][j] = cs[i][j - 1] + (c == '1');
		}
	}
	for (int i = 1 ; i <= t ; ++ i) {
		v[i] = {i - 1};
		if (i == t) {
			for (int j = 0 ; j < t ; ++ j) {
				v[i].emplace_back(j);
			}
		}
		for (int j = 1 ; j <= n ; ++ j) {
			v[i].emplace_back(l0[j][i]);
			v[i].emplace_back(l0[j][i]+1);
			v[i].emplace_back(l0[j][i]-1);
			v[i].emplace_back(l1[j][i]);
			v[i].emplace_back(l1[j][i]+1);
			v[i].emplace_back(l1[j][i]-1);
		}
		for (int j = 0 ; j < (int)v[i].size() ; ++ j) {
			if (v[i][j] < 0 || v[i][j] >= i) {
				swap(v[i][j], v[i].back());
				v[i].pop_back();
				--j;
			}
		}
		sort(v[i].begin(), v[i].end());
		v[i].resize(unique(v[i].begin(), v[i].end()) - v[i].begin());
	}
	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 : v[i]) {
			//for (int j = 0 ; j < i ; ++ j) {
				upd(dp[i][x], dp[j][x-1] + val[j][i]);
			}
		}
		for (int x = s ; x >= 1 ; -- x) {
			dp[i][x - 1] = min(dp[i][x - 1], dp[i][x]);
		}
	}
	for (int i = 1 ; i <= s ; ++ i) {
		cout << dp[t][i] << "\n";
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 5128 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 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 980 KB Output isn't correct
3 Halted 0 ms 0 KB -