oj.uz

Submission #670873

# Submission time Handle Problem Language Result Execution time Memory
670873 2022-12-11T00:59:24 Z GusterGoose27 Popeala (CEOI16_popeala) C++11
100 / 100
 288 ms 20404 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXT = 20002;
const int MAXS = 52;
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 point_pref[MAXT];
int table[MAXT+1][MAXS]; // number of subtasks (implicit), test case number, ppl. prefix min
vector<int> all_prev[MAXT];

void make_table(int i) {
	for (int j = 0; j <= t; j++) {
		for (int k = 0; k <= n; k++) {
			int prev_mn = ((j == 0) ? inf : table[j-1][k]);
			table[j][k] = min(prev_mn, dp[i][j]-point_pref[j]*k);
		}
	}
}

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];
		point_pref[i+1] = point_pref[i]+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_table(i-1);
		dp[i][0] = inf;
		for (int p = 1; p <= t; p++) {
			int num_ppl = n;
			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], table[pqry][num_ppl]+num_ppl*point_pref[p]);
				while (j < all_prev[p-1].size() && all_prev[p-1][j] == x) {
					num_ppl--;
					j++;
				}
				pqry = x;
			}
			dp[i][p] = min(dp[i][p], table[pqry][num_ppl]+num_ppl*point_pref[p]);
		}
		cout << dp[i][t] << "\n";
	}
	return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1776 KB Output is correct
2 Correct 8 ms 1832 KB Output is correct
3 Correct 8 ms 1796 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3324 KB Output is correct
2 Correct 48 ms 4208 KB Output is correct
3 Correct 55 ms 5328 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 8 ms 1776 KB Output is correct
4 Correct 8 ms 1832 KB Output is correct
5 Correct 8 ms 1796 KB Output is correct
6 Correct 34 ms 3324 KB Output is correct
7 Correct 48 ms 4208 KB Output is correct
8 Correct 55 ms 5328 KB Output is correct
9 Correct 78 ms 7624 KB Output is correct
10 Correct 115 ms 9672 KB Output is correct
11 Correct 288 ms 20012 KB Output is correct
12 Correct 246 ms 20276 KB Output is correct
13 Correct 266 ms 20404 KB Output is correct
14 Correct 260 ms 20352 KB Output is correct
15 Correct 266 ms 20340 KB Output is correct