代码

/* NOI 2019 sequence -- greedy min-cost-flow simulation.
 * Linear-time radix selection plus five intrusive binary heaps.
 */
typedef unsigned long u64;
typedef long i64;

#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>
#endif

typedef struct {
    u64 abi_version;
    const char *stdin_ptr;
    u64 stdin_size;
    char *stdout_ptr;
    u64 stdout_limit;
    u64 stdout_size;
    char *stderr_ptr;
    u64 stderr_limit;
    u64 stderr_size;
    const char *ib_ptr;
    u64 ib_limit;
    char *ob_ptr;
    u64 ob_limit;
    u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

enum { MAX_N = 200000, RADIX = 1024 };
static int av[MAX_N], bv[MAX_N], sumv[MAX_N];
static unsigned char state[MAX_N];
static int ids0[MAX_N], ids1[MAX_N], radix_count[RADIX];
static int h1data[MAX_N], f1data[MAX_N], h2data[MAX_N], f2data[MAX_N], h3data[MAX_N];

typedef struct {
    int *data;
    const int *key;
    int size;
} Heap;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    u64 *aux = (u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline unsigned rd(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned)(*p - '0') > 9) ++p;
    unsigned x = 0;
    do x = x * 10u + (unsigned)(*p++ - '0');
    while ((unsigned)(*p - '0') <= 9);
    *cursor = p;
    return x;
}

static __attribute__((always_inline)) inline void heap_sift_down(Heap *h, int pos) {
    int *d = h->data, n = h->size, x = d[pos];
    const int *key = h->key;
    for (;;) {
        int child = pos * 2 + 1;
        if (child >= n) break;
        if (child + 1 < n && key[d[child + 1]] > key[d[child]]) ++child;
        if (key[d[child]] <= key[x]) break;
        d[pos] = d[child];
        pos = child;
    }
    d[pos] = x;
}

static __attribute__((always_inline)) inline void heap_build(Heap *h) {
    for (int i = h->size / 2; i-- > 0;) heap_sift_down(h, i);
}

static __attribute__((always_inline)) inline void heap_pop(Heap *h) {
    h->data[0] = h->data[--h->size];
    if (h->size) heap_sift_down(h, 0);
}

static __attribute__((always_inline)) inline void heap_push(Heap *h, int x) {
    int pos = h->size++;
    const int *key = h->key;
    while (pos) {
        int parent = (pos - 1) >> 1;
        int y = h->data[parent];
        if (key[y] >= key[x]) break;
        h->data[pos] = y;
        pos = parent;
    }
    h->data[pos] = x;
}

static __attribute__((always_inline)) inline void clean_h1(Heap *h) {
    while (h->size && (state[h->data[0]] & 1u)) heap_pop(h);
}
static __attribute__((always_inline)) inline void clean_f1(Heap *h) {
    while (h->size && state[h->data[0]] != 2u) heap_pop(h);
}
static __attribute__((always_inline)) inline void clean_h2(Heap *h) {
    while (h->size && (state[h->data[0]] & 2u)) heap_pop(h);
}
static __attribute__((always_inline)) inline void clean_f2(Heap *h) {
    while (h->size && state[h->data[0]] != 1u) heap_pop(h);
}
static __attribute__((always_inline)) inline void clean_h3(Heap *h) {
    while (h->size && state[h->data[0]] != 0u) heap_pop(h);
}

/* Sort ids0 by the non-negative 30-bit key, ascending. */
static void radix_sort_ids(int n, const int *key) {
    int *src = ids0, *dst = ids1;
    for (int shift = 0; shift < 30; shift += 10) {
        for (int j = 0; j < RADIX; ++j) radix_count[j] = 0;
        for (int i = 0; i < n; ++i) ++radix_count[(key[src[i]] >> shift) & (RADIX - 1)];
        int off = 0;
        for (int j = 0; j < RADIX; ++j) {
            int c = radix_count[j];
            radix_count[j] = off;
            off += c;
        }
        for (int i = 0; i < n; ++i) {
            int id = src[i];
            dst[radix_count[(key[id] >> shift) & (RADIX - 1)]++] = id;
        }
        int *tmp = src; src = dst; dst = tmp;
    }
    /* Three passes leave the result in ids1. */
}

static __attribute__((always_inline)) inline char *write_i64(char *out, i64 x) {
    char tmp[24]; unsigned n = 0;
    do tmp[n++] = (char)('0' + x % 10), x /= 10; while (x);
    while (n) *out++ = tmp[--n];
    *out++ = '\n';
    return out;
}

static __attribute__((noreturn, always_inline)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall"
                     ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

int main(long argc, char **argv) {
#ifdef LOCAL
    (void)argc; (void)argv;
    static char local_in[24000000], local_out[1024];
    u64 local_size = (u64)fread(local_in, 1, sizeof local_in, stdin);
    DuckInfo local_info = {0};
    local_info.stdin_ptr = local_in; local_info.stdin_size = local_size;
    local_info.stdout_ptr = local_out; local_info.stdout_limit = sizeof local_out;
    DuckInfo *info = &local_info;
#else
    DuckInfo *info = duck_info(argc, argv);
#endif
    const char *in = info->stdin_ptr;
    char *out = info->stdout_ptr;
    int tests = (int)rd(&in);
    while (tests--) {
        int n = (int)rd(&in), k = (int)rd(&in), need = (int)rd(&in);
        for (int i = 0; i < n; ++i) av[i] = (int)rd(&in);
        for (int i = 0; i < n; ++i) {
            bv[i] = (int)rd(&in);
            sumv[i] = av[i] + bv[i];
            state[i] = 0;
            ids0[i] = i;
        }

        i64 answer = 0;
        int base = k - need;
        radix_sort_ids(n, av);
        for (int i = n - base; i < n; ++i) {
            int id = ids1[i];
            state[id] = 1;
            answer += av[id];
        }
        for (int i = 0; i < n; ++i) ids0[i] = i;
        radix_sort_ids(n, bv);
        for (int i = n - base; i < n; ++i) {
            int id = ids1[i];
            state[id] |= 2;
            answer += bv[id];
        }

        Heap h1 = {h1data, av, 0}, f1 = {f1data, av, 0};
        Heap h2 = {h2data, bv, 0}, f2 = {f2data, bv, 0};
        Heap h3 = {h3data, sumv, 0};
        int cycles = 0;
        for (int i = 0; i < n; ++i) {
            unsigned s = state[i];
            if (s == 3) ++cycles;
            else if (s == 2) h1.data[h1.size++] = i, f1.data[f1.size++] = i;
            else if (s == 1) h2.data[h2.size++] = i, f2.data[f2.size++] = i;
            else {
                h1.data[h1.size++] = i;
                h2.data[h2.size++] = i;
                h3.data[h3.size++] = i;
            }
        }
        heap_build(&h1); heap_build(&f1); heap_build(&h2); heap_build(&f2); heap_build(&h3);

        while (need--) {
            clean_h1(&h1); clean_f1(&f1); clean_h2(&h2); clean_f2(&f2); clean_h3(&h3);
            if (cycles) {
                --cycles;
                int i = h1.data[0], j = h2.data[0];
                answer += (i64)av[i] + bv[j];
                state[i] |= 1; state[j] |= 2;
                if (i == j) { ++cycles; continue; }
                if (state[i] != 3) heap_push(&f2, i); else ++cycles;
                if (state[j] != 3) heap_push(&f1, j); else ++cycles;
                continue;
            }

            int v1 = 0, v2 = 0, v3 = 0;
            if (f2.size) v1 = av[h1.data[0]] + bv[f2.data[0]];
            if (f1.size) v2 = av[f1.data[0]] + bv[h2.data[0]];
            if (h3.size) v3 = sumv[h3.data[0]];
            int best = v1 > v2 ? v1 : v2;
            if (v3 > best) best = v3;
            answer += best;

            if (v1 == best && ((v1 == v2 && state[h1.data[0]] != 2) || v1 != v2)) {
                int i = h1.data[0], j = f2.data[0];
                state[i] |= 1; state[j] |= 2;
                if (state[i] != 3) heap_push(&f2, i); else ++cycles;
            } else if (v2 == best && ((v1 == v2 && state[h1.data[0]] == 2) || v1 != v2)) {
                int i = f1.data[0], j = h2.data[0];
                state[i] |= 1; state[j] |= 2;
                if (state[j] != 3) heap_push(&f1, j); else ++cycles;
            } else {
                int i = h3.data[0];
                heap_pop(&h3);
                state[i] = 3;
            }
        }
        out = write_i64(out, answer);
    }
    info->stdout_size = (u64)(out - info->stdout_ptr);
#ifdef LOCAL
    fwrite(info->stdout_ptr, 1, info->stdout_size, stdout);
    return 0;
#else
    duck_exit();
#endif
}

评测结果