이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//""""optimized"""" lol
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vl;
const int MB = 10;
const int MA = 1<<MB;
const int LIM = MA-1;
int dp[MA][MA][MB+1];
const int MN = 100001;
int mol[MN],pt[MN],wo[MN],wk[MN];
int poc[MA];
int main() {
ios::sync_with_stdio(0);cin.tie(0);
ll n;
cin >> n;
memset(mol,0,sizeof(mol));
memset(pt,-1,sizeof(pt));
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++) {
cin >> wo[i];
}
for(int i=0;i<n;i++) {
cin >> wk[i];
}
poc[0] = 0;
for(int i=1;i<MA;i++) {
poc[i] = poc[i>>1]+(i&1);
}
for(int i=0;i<n;i++) {
int ho = wo[i]>>MB;
int lo = wo[i]&LIM;
mol[i] = 1;
for(int j=0;j<MA;j++) {
int rem = wk[i]-poc[ho&j];
if(rem < 0 || rem > MB) {continue;}
int cand = dp[j][lo][rem];
if(cand == -1) {continue;}
if(mol[cand]+1 > mol[i]) {
mol[i] = mol[cand]+1;
pt[i] = cand;
}
}
for(int j=0;j<MA;j++) {
int kt = poc[j&lo];
int dv = dp[ho][j][kt];
if(dv == -1 || mol[dv] < mol[i]) {
dp[ho][j][kt] = i;
}
}
}
int mi = 0;
for(int i=0;i<n;i++) {
if(mol[i] > mol[mi]) {
mi = i;
}
}
vl ans;
while(mi != -1) {
ans.push_back(mi);
mi = pt[mi];
}
reverse(ans.begin(),ans.end());
cout << ans.size() << '\n';
for(int i=0;i<ans.size();i++) {
if(i > 0) {cout << " ";}
cout << ans[i]+1;
}
cout << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
subsequence.cpp: In function 'int main()':
subsequence.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<ans.size();i++) {
| ~^~~~~~~~~~~
# | 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... |