oj.uz

Submission #670871

# Submission time Handle Problem Language Result Execution time Memory
670871 2022-12-11T00:47:03 Z GusterGoose27 Popeala (CEOI16_popeala) C++11
8 / 100
 47 ms 4248 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 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 0 ms 724 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3364 KB Output is correct
2 Incorrect 47 ms 4248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

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