Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MOD = 16;
- const int INF = 1e9;
- int solveFirst(const vector<int>& ronda, int m) {
- int n = (int)ronda.size();
- int ans = -INF;
- for (int c = 0; c < MOD; c++) {
- vector<vector<vector<int>>> dp(n, vector<vector<int>>(m + 1, vector<int>(MOD, -INF)));
- dp[0][0][(c + ronda[0]) % MOD] = 0;
- for (int i = 0; i < n - 1; i++) {
- for (int j = 0; j <= m; j++) {
- for (int k = 0; k < MOD; k++) {
- int a = (k + ronda[i + 1]) % MOD;
- int b = ronda[i + 1];
- dp[i + 1][j][a] = max(dp[i + 1][j][a], dp[i][j][k]);
- if (j < m)
- dp[i + 1][j + 1][b] = max(dp[i + 1][j + 1][b], dp[i][j][k] + k * k);
- }
- }
- }
- if (c == 0) {
- for (int i = 0; i < MOD; i++) {
- ans = max(ans, dp[n - 1][m - 1][i] + i * i);
- }
- } else {
- ans = max(ans, dp[n - 1][m][c]);
- }
- }
- return ans;
- }
- int solveSecond(const vector<int>& ronda, int m) {
- int n = (int)ronda.size();
- vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(MOD, -INF)));
- dp[1][1][ronda[1]] = ronda[0] * ronda[0];
- for (int i = 1; i < n - 1; i++) {
- for (int j = 1; j < m; j++) {
- for (int k = 0; k < MOD; k++) {
- int a = (k + ronda[i + 1]) % MOD;
- int b = ronda[i + 1];
- dp[i + 1][j][a] = max(dp[i + 1][j][a], dp[i][j][k]);
- if (j < m - 1)
- dp[i + 1][j + 1][b] = max(dp[i + 1][j + 1][b], dp[i][j][k] + k * k);
- }
- }
- }
- int ans = -INF;
- for (int k = 0; k < MOD; k++) {
- ans = max(ans, dp[n - 1][m - 1][k] + k * k);
- }
- return ans;
- }
- vector<int> romperonda(vector<int>& ronda, int k) {
- int n = (int)ronda.size();
- for (int i = 0; i < n; i++) {
- ronda[i] %= MOD;
- }
- return {solveFirst(ronda, k), solveSecond(ronda, k)};
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement