QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#287336 | #4207. Uplifting Excursion | Max_s_xaM | 0 | 1510ms | 3704kb | C++14 | 4.3kb | 2023-12-20 11:56:20 | 2023-12-20 11:56:22 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cstdlib>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 310;
// #include <ctime>
// int st;
int n;
ll L, a[MAXN], b[MAXN], a0, all;
ll ap[MAXN], bp[MAXN], ans = 6e18;
const int MAXT = 4e8;
int T;
int DFS(int cur, ll s, ll cnt)
{
// cout << cur << " " << s << " " << cnt << "\n";
if (cur == 1)
{
T++;
bool flag = 0;
if (s + a[1] >= 0 && s - b[1] <= 0) ans = min(ans, cnt + (s > 0 ? s : -s)), flag = 1;
if (T > MAXT)
{
if (ans == 6e18) cout << "impossible\n";
else cout << all - ans + a0 << "\n";
// cerr << 1.0 * (clock() - st) / CLOCKS_PER_SEC << "\n";
exit(0);
}
return flag;
}
if (cnt >= ans) return 2;
if (s + ap[cur] < 0 || s - bp[cur] > 0) return 2;
int tp;
if (s + cur * a[cur] <= 0)
{
for (ll i = a[cur]; i >= -b[cur]; i--)
{
tp = DFS(cur - 1, s + cur * i, cnt + (i > 0 ? i : -i));
if (tp) return tp;
}
return 0;
}
else if (s - cur * b[cur] >= 0)
{
for (ll i = -b[cur]; i <= a[cur]; i++)
{
tp = DFS(cur - 1, s + cur * i, cnt + (i > 0 ? i : -i));
if (tp) return tp;
}
return 0;
}
else
{
ll l, r;
if (s < 0) l = (-s) / cur, r = l + 1;
else l = -((s + cur - 1) / cur), r = l + 1;
bool flag = 0;
for (ll i = 0; i <= a[cur] + b[cur]; i++)
{
if (l < -b[cur] || (r <= a[cur] && s + r * cur < -(s + l * cur)))
tp = DFS(cur - 1, s + r * cur, cnt + (r > 0 ? r : -r)), r++;
else tp = DFS(cur - 1, s + l * cur, cnt + (l > 0 ? l : -l)), l--;
if (tp == 1) flag = 1;
}
return flag;
}
}
int main()
{
// st = clock();
// freopen("C.in", "r", stdin);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n), Read(L);
for (int i = n; i >= 1; i--) Read(b[i]), all += b[i];
Read(a0);
ll sum = 0;
for (int i = 1; i <= n; i++) Read(a[i]), sum += (a[i] - b[i]) * i, all += a[i];
for (int i = 1; i <= n; i++) ap[i] = ap[i - 1] + a[i] * i, bp[i] = bp[i - 1] + b[i] * i;
// cout << bp[n] << "\n";
sum = L - sum;
// cout << sum << "\n";
DFS(n, sum, 0);
if (ans == 6e18) cout << "impossible\n";
else cout << all - ans + a0 << "\n";
// cerr << 1.0 * (clock() - st) / CLOCKS_PER_SEC << " #\n";
return 0;
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 5
Accepted
time: 0ms
memory: 3704kb
input:
1 5 0 0 6
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
50 2303 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 5 25 50 0
output:
47
result:
ok single line: '47'
Test #3:
score: 0
Accepted
time: 15ms
memory: 3664kb
input:
50 -17964 18 21 8 47 11 30 0 34 11 22 10 29 14 39 25 42 16 47 6 39 0 4 28 5 4 39 43 47 14 49 24 37 22 47 23 31 18 28 43 14 44 26 46 40 27 17 41 7 13 25 27 20 17 13 23 30 9 16 5 25 46 22 35 44 34 39 19 19 33 11 30 30 41 20 1 9 39 34 31 26 28 13 13 21 45 11 32 30 35 37 22 31 1 9 43 18 31 41 34 39 2
output:
2060
result:
ok single line: '2060'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 5 3 1 0 2 0 0 2
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
10 7 0 0 0 0 0 0 0 0 0 0 7 10 5 8 10 0 9 0 4 6 2
output:
14
result:
ok single line: '14'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
50 -779348731063743410 36 40 12 5 42 47 17 35 47 44 16 45 5 41 26 7 28 23 15 27 17 19 44 18 12 30 27 13 24 5 34 11 36 39 38 32 0 34 24 11 18 26 43 50 1 29 18 28 41 38 41 19 22 0 9 30 18 36 0 21 41 7 25 10 17 9 48 9 37 7 49 13 23 9 15 25 35 10 43 27 5 45 42 33 8 30 36 20 49 24 31 42 3 27 16 45 11 33 ...
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 14ms
memory: 3640kb
input:
50 -51601 47 45 49 46 49 48 45 45 46 47 50 49 48 48 49 48 48 46 50 49 45 46 47 49 45 47 49 47 50 48 46 46 50 45 48 49 49 46 49 49 48 47 49 47 49 45 49 50 45 45 47 50 46 49 49 45 48 46 48 48 45 46 46 49 48 49 45 47 50 46 47 45 45 49 49 47 45 47 47 47 49 47 50 45 46 48 49 47 49 48 47 48 45 45 45 49 46...
output:
3319
result:
ok single line: '3319'
Test #8:
score: -5
Time Limit Exceeded
input:
50 1853 16 29 35 41 32 44 9 45 28 2 32 40 13 47 16 7 49 42 0 34 15 22 3 34 7 31 5 23 40 30 10 2 36 46 46 9 24 12 9 46 46 19 19 29 9 22 28 12 44 31 46 41 4 5 27 38 31 32 38 30 41 43 36 30 21 42 19 12 8 49 43 17 17 2 49 49 12 47 20 47 14 2 21 16 45 45 35 41 33 6 28 19 28 45 41 15 25 28 5 4 35
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Time Limit Exceeded
Test #19:
score: 10
Accepted
time: 1510ms
memory: 3652kb
input:
30 38887954194235 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 444113827766 26 511237030935 22 696666627923 315938808146 20 952560827478 924020644151 850666790939 23 587888300072 23 797812801251 911390834853 677171102320 4 2 22 950650764450 278888113729 23 15 15 13 9 637120041802 20 1...
output:
5692035643249
result:
ok single line: '5692035643249'
Test #20:
score: -10
Time Limit Exceeded
input:
30 76226675150141 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 17 25 575187266854 933205256851 30642958327 5 723752635947 251949849516 20 241825198172 10 8 19 416001319998 846220673515 292065146547 9 17 329305181338 3 153818277782 4 622464956364 2 18 543111965233 5 20 24 8
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #5:
0%
Subtask #8:
score: 0
Skipped
Dependency #6:
0%
Subtask #9:
score: 0
Skipped
Dependency #7:
0%
Subtask #10:
score: 0
Skipped
Dependency #1:
0%