# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
474949 | cs71107 | 수열 (BOI14_sequence) | C++14 | 38 ms | 1356 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;
priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;
int A[MAXN];
int vv[20][MAXN];
ll solve(int t,int n){
ll res = LINF;
if(n==1){
int curv = vv[t][0];
if(curv&1){
if(curv==1){
res = 10;
}
else {
res = 0;
for(int i=1;i<10;i++){
if((1<<i)&curv){
if(!res){
res = (i*10);
}
else {
res = 10LL*res+i;
}
}
}
}
}
else {
res = 0;
for(int i=1;i<10;i++){
if((1<<i)&curv){
res = 10LL*res+i;
}
}
}
}
else if(n==2){
res = LINF;
int a,b;
ll curres = LINF;
for(int i=0;i<9;i++){
a = vv[t][0]&(1023^(1<<i));
b = vv[t][1]&(1023^(1<<(i+1)));
vv[t+1][0] = a|b;
curres = solve(t+1,1);
if(curres){
res = min(res,curres*10LL+i);
}
else if((!i)&&(vv[t][0]&1)){
res = min(res,10LL);
}
else {
res = min(res,(ll)i);
}
}
if((vv[t][0]&512)||(vv[t][1]&1)){
a = vv[t][0]&511;
b = vv[t][1]&1022;
vv[t+1][0] = a;
vv[t+1][1] = b;
curres = solve(t+1,2);
res = min(res,curres*10LL+9);
}
}
else {
int cnt = 0;
int idx = 0;
int cur;
ll curans = LINF;
for(int tt=0;tt<10;tt++){
cnt = 0;
idx = tt;
vv[t+1][0] = 0;
for(int i=0;i<n;i++){
cur = vv[t][i]&(1023^(1<<idx));
vv[t+1][cnt]|=cur;
idx++;
if(idx==10){
idx = 0;
cnt++;
vv[t+1][cnt] = 0;
}
}
if(idx){
curans = solve(t+1,cnt+1);
}
else {
curans = solve(t+1,cnt);
}
//cout<<t<<" "<<curans<<"\n";
res = min(res,curans*10LL+tt);
}
}
return res;
}
int main()
{
int n,m,k,a,b,x,y,q;
int sum = 0;
int cnt = 0;
int mx = 0;
int mn = INF;
int cur = 0, idx = -1;
int tc;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(int i=0;i<n;i++)
{
cin>>A[i];
}
for(int i=0;i<n;i++){
vv[0][i] = (1<<A[i]);
}
ll res = solve(0,n);
cout<<res<<"\n";
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... |