Submission #1234540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234540		Vorbunny	Popeala (CEOI16_popeala)	C++20	0 / 100	10 ms	1604 KiB

popeala

#include <bits/stdc++.h>
using namespace std;

#define int long long

bool solve[55][20005];
int point[20005];
int presum[55][20005];

int query(int i, int l, int r) {
	return presum[i][r] - presum[i][l - 1];
}

int sum(int l, int r) {
	return point[r] - point[l - 1];
}

signed main() {
	int t, n, s;
	cin >> n >> t >> s;
	for (int i = 1; i <= t; i++) {
		cin >> point[i];
		point[i] += point[i-1];
	}

	char c;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= t; j++) {
			cin >> c;
			solve[i][j] = (c == '0');
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= t; j++) {
			presum[i][j] = presum[i][j-1];
			if (solve[i][j]) presum[i][j]++;
			// cout << presum[i][j] << " ";
		}
		// cout << endl;
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (presum[i][t] == 0) {
			ans += point[n];
		}
	}
	cout << ans << endl;
	s--;
	set<int> cutoff;
	cutoff.insert(t);
	int start;
	while (s--) {
		auto it = cutoff.begin();
		int start = 1;
		int addition = 1e18;
		int newcut = 0;

		for (int i = 1; i <= t; i++) {
			int tmp = 0;
			if (i == *it) {
				start = *it + 1;
				it++;
				continue;
			}
			for (int j = 1; j <= n; j++) {
				// cout << "Query: " << start << " " << i << " and " << i + 1 << " " << *it << endl;
				// cout << query(j, start, i) << " " << query(j, i + 1, *it) << endl;
				if (query(j, start, i) == 0) {
					tmp += sum(start, i);
				}
				if (query(j, i + 1, *it) == 0) {
					tmp += sum(i + 1, *it);
				}
			}
			// cout << "Cut at " << i << " cost " << tmp << endl;
			if (tmp < addition) {
				addition = tmp;
				newcut = i;
			} 
		}
		ans += addition;
		cutoff.insert(newcut);
		cout << ans << endl;
	}


}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74