QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#337352#8281. Pangu and Stoneshos_lyricWA 0ms3988kbC++142.4kb2024-02-25 11:01:302024-02-25 11:01:31

Judging History

你现在查看的是最新测评结果

  • [2024-02-25 11:01:31]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3988kb
  • [2024-02-25 11:01:30]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


constexpr int INF = 1001001001;
constexpr int MAX = 110;

int N, L, R;
int A[MAX];

int ASum[MAX];

// forest, (l, r, #)
int f[MAX][MAX][MAX];
// tree, (l, r)
int g[MAX][MAX];

int main() {
  for (; ~scanf("%d%d%d", &N, &L, &R); ) {
    for (int i = 0; i < N; ++i) {
      scanf("%d", &A[i]);
    }
    
    for (int i = 0; i < N; ++i) {
      ASum[i + 1] = ASum[i] + A[i];
    }
    
    for (int l = N; l >= 0; --l) for (int r = l + 1; r <= N; ++r) {
      for (int k = 0; k <= r - l; ++k) {
        f[l][r][k] = INF;
      }
      g[l][r] = INF;
      if (l + 1 == r) {
        g[l][r] = 0;
      } else {
        for (int i = l + 1; i < r; ++i) {
          for (int k = 1; k <= r - i; ++k) {
            chmin(f[l][r][1 + k], g[l][i] + f[i][r][k]);
          }
        }
        for (int k = 0; k <= r - l; ++k) if (L <= k && k <= R) {
          chmin(g[l][r], (ASum[r] - ASum[l]) + f[l][r][k]);
        }
      }
      chmin(f[l][r][1], g[l][r]);
// cerr<<l<<" "<<r<<": "<<g[l][r]<<"; ";pv(f[l][r],f[l][r]+(r-l+1));
    }
    printf("%d\n", (g[0][N] < INF) ? g[0][N] : -1);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3988kb

input:

3 2 2
1 2 3

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

3 2 3
1 2 3

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3880kb

input:

4 3 3
1 2 3 4

output:

-1

result:

wrong answer 1st numbers differ - expected: '0', found: '-1'