oj.uz

Submission #670870

# Submission time Handle Problem Language Result Execution time Memory
670870 2022-12-10T23:39:35 Z GusterGoose27 Popeala (CEOI16_popeala) C++11
0 / 100
 38 ms 3152 KB 
#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

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.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 74.0

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