#include <bits/stdc++.h> using namespace std; #define mk make_pair #define fi first #define sz(x) x.size() #define se second #define pb push_back #define VAR(v) #v << " = " << v << " " #define debug if(0) #define M_PI 3.14159265358979323846 typedef complex<long double> C; typedef long long ll; typedef pair<int, int> ii; typedef vector<ll> Matrix; const int maxn = (int)1e6 + 9; const int INF = (int)1e9 + 7; int mod = (int)1e9 + 7; ll a[309], n; const ll bottom = 1e13; ll ret[309]; ll bounds[309]; ll pref[309]; bool vis[309]; bool gen(int k, ll sum){ //debug cout << VAR(k) << VAR(sum) << VAR(bounds[k])<<endl; if(k == 1){ if(bounds[1] >= sum) { ret[1] = sum; return true; } return false; } ret[k] = bounds[k]; for(int i = k - 1; i >= 1; i--) bounds[i] = min(a[k - i], bounds[i] - bounds[k]); return gen(k - 1, sum - bounds[k]); } void makePref(int k) { for(int i = 1; i <= k; i++) pref[i] = pref[i-1] + ret[i]; } ll sum(int l, int r){ return pref[r] - pref[l]; } ll check(int len){ ll cnt = -INF; for(int i = len; i <= n; i++) cnt = max(cnt, sum(i - len, i)); return cnt; } vector<vector<ll>> ans; int main(int argc, char* argv[]) { ios::sync_with_stdio(false); debug; else cin.tie(NULL), cout.tie(NULL); cin>>n; for(int i = 1; i <= n; i++) cin>>a[i]; if(0){ cout<<n<<"\n"; for(int i = 1; i<=n; i++) cout<<a[i]<<" "; cout<<"\n"; } for(int k = n; k >= 1; k--) if(!vis[k]) { debug cout<<"SOLVING " << VAR(k)<<endl; for(int j = 1; j <= k; j++) bounds[k - j + 1] = a[j]; if(!gen(k, a[k])) { cout<<"NIE\n"; return 0; } debug for(int i = 1; i <= k; i++) cout<<ret[i]<<" "; debug cout << endl; makePref(k); for(int len = 1; len <= k; len++){ ll val = check(len); debug cout << VAR(len) << VAR(val) << VAR(a[len])<<endl; if(val == a[len]) vis[len] = true; } vector<ll> tmp; for(int i = 1; i <= k; i++) tmp.pb(ret[i]); ans.pb(tmp); } cout<<"TAK\n"; int length = 0; for(int i = 0; i < ans.size(); i++) length += 1 + ans[i].size(); cout<<length<<"\n"; for(int i = 0; i < ans.size(); i++) { for(ll x : ans[i]) cout<<x<<" "; cout<<-bottom<<" "; } cout<<"\n"; return 0; }
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 105 106 107 108 109 110 111 | #include <bits/stdc++.h> using namespace std; #define mk make_pair #define fi first #define sz(x) x.size() #define se second #define pb push_back #define VAR(v) #v << " = " << v << " " #define debug if(0) #define M_PI 3.14159265358979323846 typedef complex<long double> C; typedef long long ll; typedef pair<int, int> ii; typedef vector<ll> Matrix; const int maxn = (int)1e6 + 9; const int INF = (int)1e9 + 7; int mod = (int)1e9 + 7; ll a[309], n; const ll bottom = 1e13; ll ret[309]; ll bounds[309]; ll pref[309]; bool vis[309]; bool gen(int k, ll sum){ //debug cout << VAR(k) << VAR(sum) << VAR(bounds[k])<<endl; if(k == 1){ if(bounds[1] >= sum) { ret[1] = sum; return true; } return false; } ret[k] = bounds[k]; for(int i = k - 1; i >= 1; i--) bounds[i] = min(a[k - i], bounds[i] - bounds[k]); return gen(k - 1, sum - bounds[k]); } void makePref(int k) { for(int i = 1; i <= k; i++) pref[i] = pref[i-1] + ret[i]; } ll sum(int l, int r){ return pref[r] - pref[l]; } ll check(int len){ ll cnt = -INF; for(int i = len; i <= n; i++) cnt = max(cnt, sum(i - len, i)); return cnt; } vector<vector<ll>> ans; int main(int argc, char* argv[]) { ios::sync_with_stdio(false); debug; else cin.tie(NULL), cout.tie(NULL); cin>>n; for(int i = 1; i <= n; i++) cin>>a[i]; if(0){ cout<<n<<"\n"; for(int i = 1; i<=n; i++) cout<<a[i]<<" "; cout<<"\n"; } for(int k = n; k >= 1; k--) if(!vis[k]) { debug cout<<"SOLVING " << VAR(k)<<endl; for(int j = 1; j <= k; j++) bounds[k - j + 1] = a[j]; if(!gen(k, a[k])) { cout<<"NIE\n"; return 0; } debug for(int i = 1; i <= k; i++) cout<<ret[i]<<" "; debug cout << endl; makePref(k); for(int len = 1; len <= k; len++){ ll val = check(len); debug cout << VAR(len) << VAR(val) << VAR(a[len])<<endl; if(val == a[len]) vis[len] = true; } vector<ll> tmp; for(int i = 1; i <= k; i++) tmp.pb(ret[i]); ans.pb(tmp); } cout<<"TAK\n"; int length = 0; for(int i = 0; i < ans.size(); i++) length += 1 + ans[i].size(); cout<<length<<"\n"; for(int i = 0; i < ans.size(); i++) { for(ll x : ans[i]) cout<<x<<" "; cout<<-bottom<<" "; } cout<<"\n"; return 0; } |