Hướng dẫn cho Summer Contest #02 - Thật hay thách?
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors: ,
Do authors quá lười viết hướng dẫn nên chỉ để code thôi nhé! Thông cảm lần 2, hihihi~~~
C++
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SZ = 1 << 23;
char buf[SZ];
int b_ptr = 0;
int b_len = 0;
inline char nxt() {
if (__builtin_expect(b_ptr == b_len, 0)) {
b_len = fread(buf, 1, SZ, stdin);
b_ptr = 0;
if (b_len == 0) return EOF;
}
return buf[b_ptr++];
}
inline int read() {
char c = nxt();
while (c <= 32) { if (c == EOF) return 0; c = nxt(); }
int sign = 1;
if (c == '-') { sign = -1; c = nxt(); }
int res = 0;
while (c >= '0' && c <= '9') {
res = res * 10 + (c - '0');
c = nxt();
}
return res * sign;
}
const int MAX = 5000005;
uint64_t ak[MAX];
uint64_t tk[MAX];
int ai[MAX];
int ti[MAX];
int p_sum[MAX];
const int R_BITS = 12;
const int B_SZ = 1 << R_BITS;
const int B_MSK = B_SZ - 1;
int cnt[B_SZ];
void sort_r(int n) {
uint64_t *sk = ak;
uint64_t *dk = tk;
int *si = ai;
int *di = ti;
for (int sh = 0; sh < 48; sh += R_BITS) {
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i <= n; ++i) {
int b = (sk[i] >> sh) & B_MSK;
cnt[b]++;
}
int p = 0;
for (int i = 0; i < B_SZ; ++i) {
int tmp = cnt[i];
cnt[i] = p;
p += tmp;
}
for (int i = n; i >= 0; --i) {
int b = (sk[i] >> sh) & B_MSK;
int pos = cnt[b]++;
dk[pos] = sk[i];
di[pos] = si[i];
}
swap(sk, dk);
swap(si, di);
}
if (sk != ak) {
memcpy(ak, tk, (n + 1) * sizeof(uint64_t));
memcpy(ai, ti, (n + 1) * sizeof(int));
}
}
void prnt(__int128 n) {
if (n < 0) {
putchar('-');
n = -n;
}
if (n > 9) prnt(n / 10);
putchar((char)('0' + (n % 10)));
}
int32_t main() {
freopen("thatthach.inp", "r", stdin);
freopen("thatthach.out", "w", stdout);
int n = read();
if (n == 0) return 0;
int shf = 5000005;
int d1 = shf, d2 = shf;
ak[0] = ((uint64_t)d1 << 24) | d2;
ai[0] = 0;
p_sum[0] = 0;
int p0 = 0, p1 = 0, p2 = 0;
for (int i = 1; i <= n; ++i) {
int v = read();
if (v == 0) p0++;
else if (v == 1) p1++;
else p2++;
int c1 = p0 - p1 + shf;
int c2 = p1 - p2 + shf;
ak[i] = ((uint64_t)c1 << 24) | c2;
ai[i] = i;
}
for (int i = 1; i <= n; ++i) {
int v = read();
p_sum[i] = p_sum[i - 1] + v;
}
sort_r(n);
__int128 ans = 0;
bool fnd = false;
int i = 0;
while (i <= n) {
int j = i;
uint64_t ck = ak[i];
while (j <= n && ak[j] == ck) {
j++;
}
if (j - i > 1) {
int f_idx = ai[i];
__int128 mn = p_sum[f_idx];
for (int k = i + 1; k < j; ++k) {
int c_idx = ai[k];
__int128 c_sum = p_sum[c_idx] - mn;
if (!fnd || c_sum > ans) {
ans = c_sum;
fnd = true;
}
if (p_sum[c_idx] < mn) {
mn = p_sum[c_idx];
}
}
}
i = j;
}
if (fnd) {
prnt(ans);
putchar('\n');
} else {
puts("KHONG");
}
return 0;
}
Bình luận