이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int rd() {
bool neg = 0; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if(c == '-') neg = !neg;
int n = 0; while('0' <= c && c <= '9') n = (n << 3) + (n << 1) + c - '0', c = getchar();
return neg ? -n : n;
}
void wr(int n) {
static char o[11];
if(n < 0) putchar('-'), n = -n;
int i = 0; do o[i++] = n % 10 + '0'; while(n /= 10);
while(i--) putchar(o[i]);
}
inline bool ckmax(int& a, int b) {
return (a < b) ? (a = b), 1 : 0;
}
#define N 100005
int a[N], trc[N], k[N], f[1 << 10][1 << 10][11], f2[1 << 10][1 << 10][11], g[N];
int main() {
int n = rd();
for(int i = 0; i < n; ++i) {
a[i] = rd();
}
for(int i = 0; i < n; ++i) {
k[i] = rd();
}
int res = 0, pos;
for(int i = 0, l, r; i < n; ++i) {
l = a[i] >> 10;
r = a[i] & ((1 << 10) - 1);
g[i] = 1;
for(int t = 1 << 10, cur; t--; ) {
cur = __builtin_popcount(l & t);
if(cur <= k[i]) {
if(ckmax(g[i], f[t][r][k[i] - cur] + 1)) {
trc[i] = f2[t][r][k[i] - cur];
}
}
}
if(ckmax(res, g[i])) {
pos = i;
}
for(int t = 1 << 10; t--; ) {
if(ckmax(f[l][t][__builtin_popcount(r & t)], g[i])) {
f2[l][t][__builtin_popcount(r & t)] = i;
}
}
}
vector<int> seq;
while(1) {
seq.push_back(pos);
if(g[pos] == 1) {
break;
}
pos = trc[pos];
}
wr(res);
putchar('\n');
for(int i = res; i--; ) {
wr(seq[i] + 1);
putchar(' ');
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |