N1. Innoplis

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#define pii pair <int,int>
using namespace std;
using ll = long long;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n\n";
}
void cvv(vector <vector<int>> &v){
    for (int i=0;i<v.size();++i){
        for (int j=0;j<v[i].size();++j){
            cout<<v[i][j]<<' ';
        }cout<<"\n";
    }cout<<"\n\n";
}

int n;
ll S = 0,tot=-66;
vector <int> a;
vector <vector <int> > dp;
vector <bool> fst;

void fnd(int i, int j){
    cout<<"ij= "<<i<<' '<<j<<"\n";
    if (dp[i][j] == 0) return;
    if (dp[i][j] == dp[i-1][j]) {
            fst[i] = 0;
            fnd(i-1, j);
    }
    else {
            fst[i] = 1;
            fnd(i-1, j - a[i]);
    }
}


int main()
{
    cin>>n;
    a.resize(n+1);
    fst.resize(n+1);
    for (int i=1;i<=n;++i) {
            cin>>a[i];
            S+=a[i];
    }
    tot = S;
    S = S / 2;//рюкзак
    cout<<"tot= "<<tot<<"  S= "<<S<<"\n";
    dp.resize(n+1);
    for (int i=0;i<n+1;++i) dp[i].resize(S+1,0);
    for (int i=1;i<=n;++i){
        for (int j=1;j<=S;++j){
            if (j >= a[i] ){
                dp[i][j] = max(dp[i-1][j],   dp[i-1][j - a[i] ] + a[i]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cvv(dp);
    //cout<<"tot= "<<tot<<"\n";
    //cout<<"dp = "<<dp[n][S]<<"\n";
    //восстан ответ
    fnd(n, S);
    int dif = abs( (tot - dp[n][S]) - dp[n][S]);
    cout<<dif<<"\n";
    for (int i = 1; i <= n; ++i){
        if (fst[i]) cout<<1<<' ';
        else cout<<2<<' ';
    }
}
/*
5
1 2 1 4 3

2
1 1

12
10 13 14 1 20
11 12 15 4 5 6 5

12
11 12 15 4 5 6 5
10 13 14 1 20

*/