Submission #390534

#	Time	Username	Problem	Language	Result	Execution time	Memory
390534		AlexPop28	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	668 ms	81968 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

long long find_maximum(int k, vector<vector<int>> x) {
  int n = x.size();
  int m = x[0].size();
  vector<vector<int>> ans(n, vector<int>(m, -1));

  vector<vector<long long>> dp(n, vector<long long>(n / 2 + 1));
  dp[0][0] = -x[0][0];
  dp[0][1] = +x[0][m - 1];
  for (int i = 1; i < n; ++i) {
    for (int mx = 0; mx <= n / 2; ++mx) {
      dp[i][mx] = dp[i - 1][mx] - x[i][0];
      if (mx > 0) dp[i][mx] = max(dp[i][mx], dp[i - 1][mx - 1] + x[i][m - 1]);
    }
  }

  int mx = n / 2;
  for (int i = n - 1; i >= 1; --i) {
    if (dp[i][mx] == dp[i - 1][mx] - x[i][0]) {
      ans[i][0] = 0;
    } else {
      ans[i][m - 1] = 0;
      --mx;
    }
  }
  if (mx == 0) ans[0][0] = 0;
  else ans[0][m - 1] = 0;

  allocate_tickets(ans);
  return dp[n - 1][n / 2];
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10