Submission #35811

#	Time	Username	Problem	Language	Result	Execution time	Memory
35811		farmersrice	Popeala (CEOI16_popeala)	C++14	0 / 100	349 ms	10828 KiB

popeala

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#pragma GCC target ("avx,tune=native")
//Use above if bruteforcing with lots of small operations. Or just use it anytime, there's no downside. AVX is better slightly
/*
TASK: hidden
LANG: C++11
*/
using namespace std;
typedef long long ll;
typedef pair<int, int> pair2;
typedef pair<int, pair<int, int> > pair3;
typedef pair<int, pair<int, pair<int, int> > > pair4;
#define MAXN 20013
#define MAXK 53
#define INF 1000000000000000000LL
#define mp make_pair
#define add push_back
#define remove pop

//use the dp optimization found in usaco
//d and c

int n, t, k;
int values[MAXN];
ll dp[MAXK][MAXN];
string passed[MAXK];
//ll precomp[MAXN][MAXN / 316];
int lptr = 1, rptr = 0; //inclusive
int passedInRange[MAXK];
ll answer;
ll count[MAXN];

ll calc(int left, int right) {
	left--; right--;
	while (left < lptr) {
		lptr--;
		for (int i = 0; i < n; i++) {
			if (passed[i][lptr] == '1') passedInRange[i]++;
		}
		answer += values[lptr];
	}
	while (rptr < right) {
		rptr++;
		for (int i = 0; i < n; i++) {
			if (passed[i][rptr] == '1') passedInRange[i]++;
		}
		answer += values[rptr];
	}
	while (lptr < left) {
		for (int i = 0; i < n; i++) {
			if (passed[i][lptr] == '1') passedInRange[i]--;
		}
		answer -= values[lptr];
		lptr++;
	}
	while (right < rptr) {
		for (int i = 0; i < n; i++) {
			if (passed[i][rptr] == '1') passedInRange[i]--;
		}
		answer -= values[rptr];
		rptr--;
	}

	int count = 0;
	for (int i = 0; i < n; i++) {
		if (passedInRange[i] == right - left + 1) count++;
		assert(passedInRange[i] <= right - left + 1);
	}

	//cout << "Value in range " << left << ' ' << right << " is " << answer * count << endl;
	return answer * count;
}

//Copy from cbarn
void solve(int level, int left, int right, int lastleft, int lastright) {
	if (left > right) return;
	//cout << "recursing " << level << ' ' << left << ' ' << right << ' ' << lastleft << " " << lastright << " " << startingPoint << endl;

	int mid = (left + right) / 2;
	if (mid < level) return;
	int doorplaced = -1; //where is the current door placed?

	dp[level][mid] = INF;
	for (int i = min(mid, lastright); i >= max(level, lastleft); i--) {
		//cout << "dp " << level << ' ' << mid << " building off of " << dp[level - 1][i - 1] << " which is " << level - 1 << ' ' << i - 1 << endl;
		ll curBest = calc(i, mid) + dp[level - 1][i - 1];
		//cout << "done " << endl;

		if (curBest < dp[level][mid]) {
			dp[level][mid] = curBest;
			doorplaced = i;
		}
	}
	//cout << "dp " << level << " " << mid << " set to " << dp[level][mid] << " doorplaced at " << doorplaced << endl;
	//assert(dp[level][mid] >= 0);
	//assert(doorplaced >= 0);
	solve(level, left, mid - 1, lastleft, doorplaced);
	solve(level, mid + 1, right, doorplaced, lastright);
}

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);

	cin >> n >> t >> k; //num students, num tc, num batch

	for (int i = 0; i < t; i++) {
		cin >> values[i];
	}

	for (int i = 0; i < n; i++) {
		cin >> passed[i];
		//cout << "Got passed " << i << " as " << passed[i] << endl;
	}

	for (int i = 0; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = INF;
		}
		if (i != 0) dp[i][0] = INF;
	}

	for (int i = 1; i <= k; i++) {
		//cout << "Solving " << i << endl;
		solve(i, 1, t, 1, t);
		cout << dp[i][t] << endl;
	}

	//cout << dp[k][n] << endl;
}

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