Submission #35810

#TimeUsernameProblemLanguageResultExecution timeMemory
35810farmersricePopeala (CEOI16_popeala)C++14
0 / 100
353 ms10828 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...