#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;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
10696 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
10696 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
10696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
353 ms |
10828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
10696 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
10696 KB |
Output isn't correct |
