## KLIS 오버플로우 질문!

• 시나브로
<a class="problem" href="/judge/problem/read/KLIS" title="K-th Longest Increasing Sequence">KLIS</a>

예제입력과 예제입력*2를 넣어본 결과, 성공해서 그냥 입력은 문제없는것 같아,
오버플로우가 문제인 것 같은데 어디가 문제인지 잘 모르겠습니다...
오버플로우가 아니라면 또 문제가 뭘까요??

// KLIS 20190217
// #알고리즘 #프로그래밍 #종만북 #난이도:상
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
template<typename T>
void vectorclear(vector<T>& vec_obj)
{vector<T> temp_obj;
temp_obj.swap(vec_obj);}
void stringclear(string& str)
{string throwawaystr;
str.swap(throwawaystr);}
//기본셋
const long long BIGM = 2147483649;
int n,k,putn,putseq;
long long skip;
vector<int> seq;
vector<int> lis;
vector<long long> countvec;
vector<int> recon;
int cashe[500];
long long cashecount[500];

int lengthlis(int index, const vector<int>& seq)
{
if(cashe[index]!=-1){return cashe[index];}
//메모이제이션
if(index==(seq.size()-1)){return cashe[index]=1;}
//기저
int ret=1;
for(int i=1; i<seq.size()-index; i++)
{
if((seq[index]<seq[index+i]))
{ret = max(ret,1+lengthlis(index+i,seq));}
}
return cashe[index]=ret;
}

long long count(int start)
{
if(lengthlis(start,seq)==1){return 1;}
if(cashecount[start]!=-1){return cashecount[start];}
long long ret=0;
for(int next=start+1;next<n;next++)
{
if(((seq[start]<seq[next])&&(lengthlis(start,seq)==lengthlis(next,seq)+1)))
{
ret = min<long long>(BIGM,ret+count(next));}
}
return cashecount[start]=ret;
}

void reconst(int start)
{if(start!=0){recon.push_back(seq[start]);}
vector<pair<int,int>> sets;
vectorclear(sets);
for(int next=start+1;next<n;next++)
{if((seq[start]<seq[next])&&(lengthlis(start,seq)==lengthlis(next,seq)+1))
{sets.push_back(make_pair(seq[next],next));}}
sort(sets.begin(),sets.end());
for(int i=0;i<sets.size();i++)
{
int idx=sets[i].second;
long long counts=count(idx);
if(skip>=counts)
{skip-=counts;}
else
{reconst(idx);break;}
}
}

int main()
{
memset(cashe,-1,sizeof(cashe));
int C;
cin>>C;
while(C--)
{
vectorclear(seq);
vectorclear(lis);
vectorclear(countvec);
vectorclear(recon);
cin>>n>>k;
skip=k-1;
putn=n;
seq.push_back(0);
while(putn--)
{cin>>putseq;
seq.push_back(putseq);}
n+=1;
//for(int i=0;i<n;i++)
//{memset(cashe,-1,sizeof(cashe));
//lis.push_back(lengthlis(i, seq));}
memset(cashe,-1,sizeof(cashe));
memset(cashecount,-1,sizeof(cashecount));
for(int i=0;i<n;i++)
{countvec.push_back(count(i));}
//count까지 세팅
reconst(0);
cout<<recon.size()<<endl;
for(int i=0; i<recon.size(); i++)
{cout<<recon[i]<<" ";}
cout<<endl;
}
return 0;
}


1년 전
##### 0개의 댓글이 있습니다.
• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.