# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
465424 | Yuisuyuno | Longest beautiful sequence (IZhO17_subsequence) | C++14 | 6031 ms | 5336 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define bc(x) __builtin_popcount(x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 100005
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long
using namespace std;
typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;
int n;
int a[N];
int k[N];
void readfile()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
if (fopen(Task".inp","r"))
{
freopen(Task".inp","r",stdin);
//freopen(Task".out","w",stdout);
}
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++) cin >> k[i];
}
int dp[N];
int Mx[N], ptr;
int trc[N];
void proc()
{
for(int i=1; i<=n; i++) dp[i] = 1;
int mx=1, ptr=1;
for(int i=1; i<=n; i++){
Mx[i] = max(Mx[i-1],dp[i]);
if (bc(a[i]) < k[i]) continue;
for(int j=i-1; j>=1; j--){
if (bc(a[i] & a[j])==k[i]){
if (dp[j] >= dp[i]){
dp[i] = dp[j]+1;
trc[i] =j;
}
if (dp[i] > mx){
mx = dp[i];
ptr = i;
}
}
if (Mx[j] < dp[i]) break;
}
Mx[i] = max(Mx[i-1],dp[i]);
}
vector<int> ans;
while (ptr){
ans.pb(ptr);
ptr=trc[ptr];
}
reverse(all(ans));
cout << ans.size() << '\n';
for(auto x : ans) cout << x << ' ';
}
signed main()
{
readfile();
proc();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |