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; 
    }
    

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