QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#427444#8780. Training, Round 2中国入民小学附属信息I队 (Zicheng Wang, Shubang Liu, Minkai Shao)#RE 553ms16532kbC++143.7kb2024-06-01 13:20:162024-06-01 13:20:18

Judging History

This is the latest submission verdict.

  • [2024-06-01 13:20:18]
  • Judged
  • Verdict: RE
  • Time: 553ms
  • Memory: 16532kb
  • [2024-06-01 13:20:16]
  • Submitted

answer

#include <iostream>
#include <algorithm>
#include <bitset>

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 = 5005;

int n, A, B;
int al[MAXN], ar[MAXN], bl[MAXN], br[MAXN];

bitset <MAXN> pre[MAXN], suf[MAXN];
bitset <MAXN> f[2][MAXN], g;

int main()
{
    // freopen("M.in", "r", stdin);
    // freopen("M.out", "w", stdout);
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n), Read(A), Read(B);
    int _n = 0;
    for (int i = 1, x1, y1, x2, y2; i <= n; i++)
    {
        Read(x1), Read(y1), Read(x2), Read(y2);
        if (y1 < A || y2 < B) continue;
        _n++;
        al[_n] = max(0, x1 - A), ar[_n] = y1 - A;
        bl[_n] = max(0, x2 - B), br[_n] = y2 - A;
    }
    n = _n;
    for (int i = 1; i <= n; i++) ar[i] = min(ar[i], n), br[i] = min(br[i], n);
    pre[0].set(0);
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1], pre[i].set(i);
    suf[n].set(n);
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1], suf[i].set(i);
    // cout << n << "\n";
    // for (int i = 1; i <= n; i++) cout << al[i] << ' ' << ar[i] << ' ' << bl[i] << ' ' << br[i] << "\n";

    int p = 0;
    f[0][0].set(0);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++) f[p ^ 1][j] = f[p][j];
        for (int j = al[i]; j < i && j <= ar[i]; j++)
        {
            if (f[p][j].none()) continue;
            g = f[p][j], g &= pre[br[i]], g &= suf[bl[i]];
            if (g.none()) continue;
            f[p ^ 1][j + 1] |= g, f[p ^ 1][j] |= g << 1;
        }
        p ^= 1;
        // for (int j = 0; j <= i; j++, cout << '\n')
        //     for (int k = 0; k <= i; k++)
        //     {
        //         cout << f[p][j][k] << ' ';
        //     }
    }
    int ans = 0;
    for (int i = 0; i <= n; i++)
        for (int j = 0; i + j <= n; j++)
            if (f[p][i].test(j)) ans = max(ans, i + j);
    cout << ans << '\n';
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9680kb

input:

3 0 0
0 1 0 1
1 1 0 1
1 1 1 1

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 553ms
memory: 16532kb

input:

5000 801577551 932138594
801577551 801577551 932138594 932138594
801577552 801577552 932138594 932138594
801577552 801577552 932138595 932138595
801577552 801577552 932138596 932138596
801577553 801577553 932138596 932138596
801577553 801577553 932138597 932138597
801577553 801577553 932138598 93213...

output:

5000

result:

ok single line: '5000'

Test #3:

score: -100
Runtime Error

input:

5000 932138594 801577551
932138594 932138594 801577551 801577551
932138594 932138594 801577552 801577552
932138595 932138595 801577552 801577552
932138596 932138596 801577552 801577552
932138596 932138596 801577553 801577553
932138597 932138597 801577553 801577553
932138598 932138598 801577553 80157...

output:


result: