QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#287338#4207. Uplifting ExcursionMax_s_xaM0 3893ms3600kbC++144.3kb2023-12-20 11:58:052023-12-20 11:58:05

Judging History

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

  • [2023-12-20 11:58:05]
  • 评测
  • 测评结果:0
  • 用时:3893ms
  • 内存:3600kb
  • [2023-12-20 11:58:05]
  • 提交

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 = 1e9;
int T;


int DFS(int cur, ll s, ll cnt)
{
    // cout << cur << " " << s << " " << cnt << "\n";
    T++;
    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);
    }
    if (cur == 1)
    {
        
        bool flag = 0;
        if (s + a[1] >= 0 && s - b[1] <= 0) ans = min(ans, cnt + (s > 0 ? s : -s)), flag = 1;
        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: 1ms
memory: 3600kb

input:

1 5
0 0 6

output:

5

result:

ok single line: '5'

Test #2:

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

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: 17ms
memory: 3424kb

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: 3468kb

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: 3420kb

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: 3472kb

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: 15ms
memory: 3424kb

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: 3490ms
memory: 3464kb

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: 0
Accepted
time: 3483ms
memory: 3428kb

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:

5959550686625

result:

ok single line: '5959550686625'

Test #21:

score: 0
Accepted
time: 3893ms
memory: 3468kb

input:

30 783
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 842682060204 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 5 812222496404 0

output:

842682060231

result:

ok single line: '842682060231'

Test #22:

score: 0
Accepted
time: 3452ms
memory: 3480kb

input:

30 63681107909129
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 26 29 28 25 28 162867113393 396607890615 26 27 29 27 29 29 98874364794 27 26 28 25 28 298317942689 473749524449 27 29 25 29 738708341359 378923162064 903755880355 985915633657 113061161327 29

output:

3130974862204

result:

ok single line: '3130974862204'

Test #23:

score: -10
Time Limit Exceeded

input:

30 1000000001687
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 11 999999999991 13 317621530099 581606427561 21 5 7 27 6 459097506433 15 6 29 13 29 9 25 11 10 23 17 14 6 25 11 21 10 5 16 19

output:

1000000000571

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%