QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#337352 | #8281. Pangu and Stones | hos_lyric | WA | 0ms | 3988kb | C++14 | 2.4kb | 2024-02-25 11:01:30 | 2024-02-25 11:01:31 |
Judging History
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'