Submission #712508

#	Time	Username	Problem	Language	Result	Execution time	Memory
712508		vjudge1	Tortoise (CEOI21_tortoise)	C++11	48 / 100	3074 ms	430904 KiB

tortoise

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _all(i, a, b) for (int i = (a); i <= (int)(b); ++i)
int D[603][302][302][2];  /// 当前时间、当前位置、山数、手数 ->
                          ///  最后一座山的位置
const int INF = 0x3f3f3f3f;
int solve(int n) {
  int ans = 0;
  vector<int> A(n + 1), S(n + 1);
  _all(i, 1, n) cin >> A[i], S[i] = S[i - 1] + max(A[i], 0);
  memset(D, 0x3f, sizeof(D));
  D[0][1][0][0] = 0;
  _all(t, 0, 2 * n + 1) _all(i, 1, n) _all(j, 0, n) {
    int *d = D[t][i][j];
    _all(c, 0, 1) if (d[c] < INF) ans = max(ans, j);  // 更新答案
    /// 不打发时间的活动
    if (A[i] == -1) d[0] = min(d[0], d[1]);         /// 放在山里
    if (A[i] > 0 && d[0] < S[i] && i + i - 2 >= t)  // 假的?
      D[t][i][j + 1][1] = min(D[t][i][j + 1][1], max(d[0], S[i - 1]) + 1);
    _all(c, 0, 1) {  /// 移动
      D[t + 1][i - 1][j][c] = min(D[t + 1][i - 1][j][c], d[c]);
      D[t + 1][i + 1][j][c] = min(D[t + 1][i + 1][j][c], d[c]);
    }
  }
  return S[n] - ans;
}
int main() {
  for (int n; cin >> n;)
    printf("%d\n", solve(n));
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27