QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#184606 | #3872. Gym Badges | Talaodi | 0 | 15ms | 101888kb | C++14 | 4.8kb | 2023-09-20 22:29:52 | 2023-09-20 22:29:53 |
Judging History
answer
#include <bits/stdc++.h>
char __ST__;
namespace IO {
template <class Stream>
Stream& fmtbase(Stream& out, const char* format) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
throw std::invalid_argument("Error Number of Parameters!");
}
out << *format;
}
return out;
}
template <class Stream, class Fst, class... Nxt>
Stream& fmtbase(Stream& out, const char* format, const Fst& value, const Nxt&... nxt) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
out << value;
return fmtbase(out, format + 2, nxt...);
}
out << *format;
}
throw std::invalid_argument("Error Number of Parameters!");
}
template <class... Ps>
std::string to_string(const char* format, const Ps&... ps) {
std::stringstream ss;
fmtbase(ss, format, ps...);
return ss.str();
}
template <class... Ps>
std::ostream& fmtout(const char* format, const Ps&... ps) {
return fmtbase(std::cout, format, ps...);
}
template <class... Ps>
std::ostream& fmterr(const char* format, const Ps&... ps) {
return fmtbase(std::cerr, format, ps...);
}
std::istream& allin() {
return std::cin;
}
template <class Fst, class ... Nxt>
std::istream& allin(Fst& fst, Nxt&... nxt) {
std::cin >> fst;
return allin(nxt...);
}
template <class Iter>
std::istream& rangin(Iter begin, Iter end) {
while (begin != end) {
std::cin >> *begin;
begin++;
}
return std::cin;
}
namespace Fast {
bool sync = false;
char buf[1 << 23];
char *p1 = buf, *p2 = buf;
void sync_with_ios(bool s) {
sync = s;
}
char getchar() {
if (sync) {
return (char) std::cin.get();
}
else {
if (p1 == p2) {
p1 = buf;
p2 = p1 + fread(buf, 1, 1 << 22, stdin);
}
if (p1 == p2) {
return EOF;
}
else {
char res = *p1;
p1++;
return res;
}
}
}
void read() { }
template <class T, class... U>
void read(T& x, U&... us) {
x = 0;
T pos = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') {
pos = -1;
}
c = getchar();
}
while (isdigit(c)) {
x = 10 * x + c - '0';
c = getchar();
}
x *= pos;
read(us...);
}
template <class T>
void write(const T& t) {
if (t > 10) {
write(t / 10);
}
std::cout << (int) (t % 10);
}
}
}
namespace Solve {
using namespace IO;
using ll = long long;
using ul = unsigned long long;
using db = double;
using ld = long double;
using ui = unsigned int;
using ib = __int128;
using ub = __uint128_t;
int const INF = std::numeric_limits<int>::max();
int const NINF = std::numeric_limits<int>::min();
ll const LINF = std::numeric_limits<ll>::max();
ll const LNINF = std::numeric_limits<ll>::min();
ld const EPS = 1e-6;
template <class T>
inline int isz(const T& v) {
return v.size();
}
std::mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) {
return std::uniform_int_distribution<ll>(l, r)(mt);
}
int const N = 5e3 + 10;
struct Val {
int L, X;
};
Val v[N + 1];
int f[N + 1][N + 1];
int n;
void main() {
std::cin >> n;
for (int i = 1; i <= n; i++) {
std::cin >> v[i].X;
}
for (int i = 1; i <= n; i++) {
std::cin >> v[i].L;
}
std::sort(v + 1, v + n + 1, [&](const Val& a, const Val& b) {
return a.L + a.X < b.L + b.X;
});
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
f[i][j] = INF;
}
}
f[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (f[i][j] == INF) {
continue;
}
if (f[i][j] <= v[i + 1].L) {
f[i + 1][j + 1] = std::min(f[i + 1][j + 1], f[i][j] + v[i + 1].X);
}
f[i + 1][j] = std::min(f[i + 1][j], f[i][j]);
}
}
for (int i = 2; i <= n; i++) {
if (f[n][i] == INF) {
break;
}
assert(f[n][i] - f[n][i - 1] >= f[n][i - 1] - f[n][i - 2]);
}
}
void init() {
}
void clear() {
}
}
char __ED__;
signed main() {
#ifndef ONLINE_JUDGE
auto input_file = freopen("d.in", "r", stdin);
auto output_file = freopen("d.out", "w", stdout);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
// std::cin >> t;
Solve::init();
for (int id = 1; id <= t; id++) {
Solve::main();
Solve::clear();
}
#ifndef ONLINE_JUDGE
std::cout.flush();
fclose(input_file);
fclose(output_file);
#endif
#ifndef ONLINE_JUDGE
IO::fmterr("{}{}static memory usage: {} MB.\n", std::fixed, std::setprecision(3), (&__ST__ - &__ED__) / 1024. / 1024);
#endif
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5836kb
input:
8 539270098 632706230 269629236 114860227 516388668 106926736 442326081 489479590 349109371 304195858 1 1 1 1 1 272176035
output:
result:
wrong answer 1st lines differ - expected: '2', found: ''
Subtask #2:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
499024 24194059 58419582 93795671 46748573 538530 94101772 6557176 45861806 13697565 74131600 86230763 495874 93328371 85034659 58261516 3311420 83620814 92145308 62793177 67970802 63891191 62175600 59686038 44916927 32817940 23191454 40796822 55385422 97662235 82408332 33350127 65553532 70025555 47...
output:
result:
Subtask #3:
score: 0
Wrong Answer
Test #41:
score: 0
Wrong Answer
time: 15ms
memory: 101888kb
input:
4920 343676952 471362068 183764630 14272498 286605010 453007536 667797750 174763306 161753738 692259390 402384334 207809675 24816038 135559720 2349171 268297289 158915976 311483232 237276350 130673100 523233652 177852180 84082840 350906472 27172979 107661274 8628817 205814954 636498502 115751626 451...
output:
result:
wrong answer 1st lines differ - expected: '200', found: ''
Subtask #4:
score: 0
Skipped
Dependency #1:
0%