Submission #2318

#	Time	Username	Problem	Language	Result	Execution time	Memory
2318		sebin	생일수 I (GA4_birthday1)	C++98	100 / 100	868 ms	13096 KiB

birthday1

#include <iostream>

using namespace std;

int d[1000001],a[1000001],s[1000001],sp;
int main()
{
    int t,n,l,i,j,k,c;
    int birth_num[3]={3,5,8};
    cin >> t;
    for(l=1;l<=t;l++){
        cin >> n;
        for(i=0;i<=n;i++) d[i]=999999;
        for(i=0;i<3;i++){
            k=birth_num[i];
            d[k]=1; a[k]=k;
            for(j=k+1;j<=n;j++){
                if(d[j-k]==999999)continue;
                if(d[j-k]+1<d[j]){
                    d[j]=d[j-k]+1;
                    a[j]=k;
                }
                else if(d[j-k]+1==d[j]){
                    if(j-k<j-a[j]){
                        d[j]=d[j-k]+1;
                        a[j]=k;
                    }
                }
            }
        }
        if(d[n]==999999) cout << "-1" << endl;
        else{
            sp=0;
            c=n;
            while(c>0){
                sp++;
                s[sp]=a[c];
                c=c-a[c];
            }
            for(i=sp;i>=1;i--) cout << s[i];
            cout << endl;
        }
    }
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 19 / 19
• Subtask 3: 26 / 26
• Subtask 4: 41 / 41