QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288321#138. Bali SculpturesMax_s_xaM0 2ms3608kbC++143.3kb2023-12-22 15:01:512023-12-22 15:01:52

Judging History

This is the latest submission verdict.

  • [2023-12-22 15:01:52]
  • Judged
  • Verdict: 0
  • Time: 2ms
  • Memory: 3608kb
  • [2023-12-22 15:01:51]
  • Submitted

answer

#include <iostream>
#include <algorithm>

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 = 110, MAXM = 2010;

int n, L, R;
ll a[MAXM], sum[MAXN];

int f[MAXM];
inline void Solution1()
{
    ll msk = 0, res = 0;
    for (int s = 41; s >= 0; s--)
    {
        msk ^= (1ll << s);
        f[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            f[i] = 2e9;
            for (int j = 0; j < i; j++)
                if (((sum[i] - sum[j]) & msk) == res)
                    f[i] = min(f[i], f[j] + 1);
        }
        if (f[n] > R) res ^= (1ll << s);
    }
    Write(res, '\n');
}

bool g[MAXN][MAXN];
inline void Solution2()
{
    ll msk = 0, res = 0;
    for (int s = 41; s >= 0; s--)
    {
        msk ^= (1ll << s);
        g[0][0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= R; j++) g[i][j] = 0;
            for (int j = 0; j < i; j++)
                if (((sum[i] - sum[j]) & msk) == res)
                {
                    for (int k = 1; k <= R; k++)
                        g[i][k] |= g[j][k - 1];
                }
        }
        bool flag = 0;
        for (int i = L; i <= R; i++)
            if (g[n][i]) {flag = 1; break;}
        if (!flag) res ^= (1ll << s);
    }
    Write(res, '\n');
}

int main()
{
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n), Read(L), Read(R);
    for (int i = 1; i <= n; i++) Read(a[i]), sum[i] = sum[i - 1] + a[i];
    if (L == 1) Solution1();
    else Solution2();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3428kb

input:

8 1 4
1 2 1 1 1 0 4 6

output:

7

result:

wrong answer 1st lines differ - expected: '6', found: '7'

Subtask #2:

score: 0
Wrong Answer

Test #13:

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

input:

6 2 3
1 1 1 1 1 1

output:

2

result:

ok single line: '2'

Test #14:

score: -0
Wrong Answer
time: 1ms
memory: 3476kb

input:

20 4 7
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

output:

31

result:

wrong answer 1st lines differ - expected: '30', found: '31'

Subtask #3:

score: 0
Wrong Answer

Test #26:

score: 0
Wrong Answer
time: 1ms
memory: 3604kb

input:

5 1 3
451631570 250518388 397580948 477427142 699144811

output:

1073741823

result:

wrong answer 1st lines differ - expected: '1040187263', found: '1073741823'

Subtask #4:

score: 0
Wrong Answer

Test #36:

score: 0
Accepted
time: 1ms
memory: 3404kb

input:

21 1 20
7 2 8 9 5 5 2 8 3 0 5 0 5 9 3 4 1 4 7 7 10

output:

15

result:

ok single line: '15'

Test #37:

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

input:

50 1 10
8 8 6 4 10 8 2 2 5 4 6 3 3 7 2 4 8 1 3 9 9 6 4 4 10 8 1 5 4 10 7 1 6 5 7 5 3 5 9 1 8 4 10 2 10 2 3 1 4 4

output:

31

result:

ok single line: '31'

Test #38:

score: -0
Wrong Answer
time: 1ms
memory: 3472kb

input:

25 1 10
4 0 8 2 7 2 6 9 10 3 4 1 4 8 4 4 7 7 10 9 5 0 8 3 10

output:

31

result:

wrong answer 1st lines differ - expected: '23', found: '31'

Subtask #5:

score: 0
Wrong Answer

Test #46:

score: 0
Accepted
time: 1ms
memory: 3348kb

input:

51 1 20
6 10 12 9 0 3 14 3 0 1 18 20 4 9 7 16 11 15 17 16 10 15 11 1 6 16 19 15 12 17 10 3 6 5 14 6 11 0 18 6 0 2 4 7 7 16 7 9 10 13 0

output:

31

result:

ok single line: '31'

Test #47:

score: 0
Accepted
time: 1ms
memory: 3356kb

input:

65 1 10
4 4 16 20 4 4 1 16 19 7 7 6 7 13 3 17 6 1 18 4 18 11 10 5 6 16 19 12 15 11 1 2 11 9 17 2 3 18 18 4 14 19 6 8 0 16 7 5 17 10 1 12 2 7 17 15 12 13 18 2 12 7 12 8 14

output:

79

result:

ok single line: '79'

Test #48:

score: 0
Accepted
time: 1ms
memory: 3524kb

input:

78 1 23
1 7 6 6 16 19 4 1 3 19 4 11 14 5 11 6 18 15 3 19 1 16 3 11 9 18 4 3 16 5 15 20 19 16 20 15 7 11 4 13 8 5 11 16 5 19 10 0 11 13 16 3 9 13 13 4 9 4 8 18 4 15 15 1 1 2 15 19 9 9 12 14 1 12 10 16 9 1

output:

47

result:

ok single line: '47'

Test #49:

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

input:

91 1 55
17 10 12 19 18 1 10 7 15 15 10 8 1 4 20 1 6 4 11 11 2 3 17 5 20 4 11 6 6 20 1 0 2 5 19 15 9 20 18 1 2 17 14 5 11 14 13 12 11 13 4 16 20 8 13 6 0 7 15 10 15 2 19 17 0 16 17 16 18 2 3 13 12 7 20 6 1 17 6 4 5 19 11 18 5 19 12 17 15 8 11

output:

31

result:

ok single line: '31'

Test #50:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

100 1 100
14 12 3 1 15 7 6 13 16 16 0 2 12 5 13 6 18 18 3 5 13 14 5 19 12 20 2 1 2 4 13 14 4 13 9 12 4 20 1 10 10 19 10 5 1 7 3 15 9 4 2 9 10 20 15 10 11 13 5 12 2 15 8 1 18 5 7 15 4 11 9 18 20 14 10 8 9 10 18 10 11 0 7 12 6 15 19 0 9 0 15 19 0 2 20 0 9 1 20 17

output:

31

result:

ok single line: '31'

Test #51:

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

input:

100 1 100
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20...

output:

20

result:

ok single line: '20'

Test #52:

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

input:

100 1 1
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2...

output:

2000

result:

ok single line: '2000'

Test #53:

score: -0
Wrong Answer
time: 1ms
memory: 3428kb

input:

100 1 47
18 1 15 15 2 14 19 16 8 19 1 7 12 5 16 1 5 15 13 15 16 20 8 20 9 13 7 19 8 2 4 4 4 17 5 19 19 16 2 5 13 19 9 19 5 14 17 7 12 13 16 8 7 20 10 20 7 14 19 2 9 8 11 18 19 12 9 13 20 16 10 15 9 16 17 6 20 2 19 20 15 20 8 11 12 4 20 18 1 13 8 1 9 16 12 18 17 1 3 19

output:

63

result:

wrong answer 1st lines differ - expected: '47', found: '63'

Subtask #6:

score: 0
Wrong Answer

Test #55:

score: 0
Wrong Answer
time: 0ms
memory: 3352kb

input:

51 1 20
112872931 738945953 683278169 770763749 516510818 790818428 875172481 703986370 60868760 918060338 785761560 775662511 633498896 598270657 590667589 115223551 657182582 662359373 423527461 442741161 404625684 341975402 396747626 126186088 753822361 159840892 743886212 135361223 217348329 815...

output:

2147483647

result:

wrong answer 1st lines differ - expected: '1879048191', found: '2147483647'

Subtask #7:

score: 0
Wrong Answer

Test #63:

score: 0
Wrong Answer
time: 2ms
memory: 3484kb

input:

90 45 90
0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2

output:

3

result:

wrong answer 1st lines differ - expected: '2', found: '3'

Subtask #8:

score: 0
Wrong Answer

Test #74:

score: 0
Wrong Answer
time: 1ms
memory: 3608kb

input:

101 1 20
109288331 167187936 289459547 455669706 656308194 233503022 562258473 2210429 243994669 58628149 750503963 610269250 29072940 251143410 458350486 696874700 870849343 646709707 646709077 746808795 87439926 187779526 762073671 569489420 380238922 982163795 784978520 933220915 264403502 755738...

output:

3221225471

result:

wrong answer 1st lines differ - expected: '3221159935', found: '3221225471'

Subtask #9:

score: 0
Skipped

Dependency #1:

0%

Subtask #10:

score: 0
Skipped

Dependency #1:

0%

Subtask #11:

score: 0
Skipped

Dependency #1:

0%

Subtask #12:

score: 0
Skipped

Dependency #1:

0%

Subtask #13:

score: 0
Skipped

Dependency #1:

0%