Submission #670870

#	Time	Username	Problem	Language	Result	Execution time	Memory
670870		GusterGoose27	Popeala (CEOI16_popeala)	C++11	0 / 100	38 ms	3152 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXT = 20000;
const int MAXS = 50;
const int inf = 2e9;
int n, t, s;
int points[MAXT];

int dp[MAXS+1][MAXT+1];
bool solved[MAXS][MAXT];
int prv[MAXS][MAXT];
int table[MAXT][16];
vector<int> all_prev[MAXT];

void make_sparse(int x) {
	for (int i = 0; i < t; i++) table[i][0] = dp[x][i];
	for (int i = 1; i < 16; i++) {
		for (int j = 0; j < t; j++) {
			int np = j+(1<<(i-1));
			if (np >= t) break;
			table[j][i] = min(table[j][i-1], table[np][i-1]);
		}
	}
}

int rmq(int l, int r) {
	int p = 31-__builtin_clz(r-l+1);
	return min(table[l][p], table[r-(1<<p)+1][p]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> t >> s;
	for (int i = 0; i < t; i++) cin >> points[i];
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		int p = -1;
		for (int j = 0; j < t; j++) {
			solved[i][j] = s[j]-'0';
			if (!solved[i][j]) p = j;
			prv[i][j] = p;
			if (p >= 0) all_prev[j].push_back(p);
		}
	}
	for (int i = 0; i < t; i++) {
		sort(all_prev[i].begin(), all_prev[i].end(), greater<int>());
	}
	fill(dp[0]+1, dp[0]+t+1, inf);
	for (int i = 1; i <= s; i++) {
		make_sparse(i-1);
		dp[i][0] = inf;
		for (int p = 1; p <= t; p++) {
			int cur_add = n*points[p-1];
			int pqry = p-1;
			dp[i][p] = inf;
			for (int j = 0; j < all_prev[p-1].size();) {
				int x = all_prev[p-1][j];
				if (pqry > x) dp[i][p] = min(dp[i][p], cur_add+rmq(x+1, pqry));
				while (j < all_prev[p-1].size() && all_prev[p-1][j] == x) {
					cur_add -= points[p-1];
					j++;
				}
				pqry = x;
			}
			dp[i][p] = min(dp[i][p], cur_add+rmq(0, pqry));
		}
		cout << dp[i][t] << "\n";
	}
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for (int j = 0; j < all_prev[p-1].size();) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:63:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while (j < all_prev[p-1].size() && all_prev[p-1][j] == x) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~~

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