Submission #670871

#	Time	Username	Problem	Language	Result	Execution time	Memory
670871		GusterGoose27	Popeala (CEOI16_popeala)	C++11	8 / 100	47 ms	4248 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 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 (stderr)

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 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74