HackerEarth/078_Class Homework--1.cpp at master · upadhysh/HackerEarth · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <vector>
#include <string>
#define ll long long
using namespace std;
int main(){
    int t;cin>>t;
    for(int ctr=1;ctr<=t;ctr++){
        vector<vector<ll> > two(21,vector<ll> (21,-1));
        vector<vector<ll> > one(21,vector<ll> (21,-1));
        string s;cin>>s;
        // cout<<ctr<<"*"<<s<<" ";
        int n=s.size();
        if(n<4){
            cout<<"unlucky"<<endl;
            continue;
        }
        for(int i=0;i<n;i++){
            one[i][i]=s[i]-'0';
            // if(one[i][i]==0)one[i][i]=-1;
        }


        for(int i=0,j;i<n;i++){
            ll sum=0;
            if(s[i]=='0')continue;
            for(j=i;j<n && j<i+12;j++){
                sum*=10;
                sum+=s[j]-'0';
                one[i][j]=sum;
            }
            sum*=10;
            if(j<n)if(sum+s[j]-'0'==1000000000000)one[i][j]=sum+s[j]-'0';
        }


        for(int win=1;win<n;win++){
            for(int i=0,j=win;j<n;j++,i++){
                for(int k=i;k<=j-1;k++){
                    if(one[i][k] !=-1 && one[k+1][j]!=-1 ){
                    // if(one[i][k]>0 && one[k+1][j]>0 ){
                        two[i][j]=max(two[i][j],one[i][k]+one[k+1][j]);
                        // cout<<one[i][k]<<" "<<one[k+1][j]<<"*"<<k<<" "<<one[i][k]+one[k+1][j]<<endl;
                    }
                    //one[i][k]>0 && one[k+1][j]!=-1 &&
                //     if( one[i][k]!=-1 && one[k+1][j]!=-1 && one[i][j]==-1){
                //         // cout<<one[i][k] << one[k+1][j]<<one[i][j]<<"**"<<endl;
                //         if(one[i][k]==0 && one[k+1][j]==0){one[i][j]=0;}
                //         else {
                //             one[i][j] = one[i][k];
                //             // while(t){
                //             //     one[i][j]*=10;
                //             //     one[i][j]+=t%10;
                //             //     t/=10;
                //             // }
                //             for(int te=k+1;te<=j;te++){
                //                 one[i][j]*=10;
                //             }
                //             one[i][j]+=one[k+1][j];
                //         }
                //     }
                //     // cout<<i<<" "<<j<<"*"<<one[i][j]<<endl;
                //     // cout<<i<<" "<<j<<"^"<<two[i][j]<<endl;
                // }
                // if(win>=12){
                //     one[i][j]=-1;
                //     continue;
                }
                // cout<<"**********"<<endl;
                // if(one[i][j-1]!=0)one[i][j]=one[i][j-1]*10+((one[j][j]==-1)?0:one[j][j]);

            }

        }

        // for(int i=0;i<n;i++){
        //     for(int j=0;j<n;j++){
        //         cout<<one[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        // cout<<"*************"<<endl;
        // for(int i=0;i<n;i++){
        //     for(int j=0;j<n;j++){
        //         cout<<two[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }

        ll ret = -1 ;
        for(int i=0;i<n;i++){
            // cout<<i<<"-"<<two[0][i]<<" "<<two[i+1][n-1]<<endl;
            if(two[0][i] == -1 || two[i+1][n-1] == -1 )continue;
            // cout<<i<<"*"<<two[0][i] + two[i+1][n-1]<<endl;
            ret = max(ret , two[0][i] + two[i+1][n-1]);
        }

        if(ret!=-1)cout<<ret<<endl;
        else cout<<"unlucky"<<endl;
    }
    return 0;
}