daily pastebin goal
68%
SHARE
TWEET

Untitled

a guest May 14th, 2018 45 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define x first
  6. #define y second
  7. #define mp make_pair
  8. #define pb push_back
  9. #define sqr(a) ((a) * (a))
  10. #define sz(a) int(a.size())
  11. #define all(a) a.begin(), a.end()
  12. #define forn(i, n) for(int i = 0; i < int(n); i++)
  13. #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
  14.  
  15. typedef long long li;
  16. typedef long double ld;
  17. typedef pair<int, int> pt;
  18.  
  19. template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
  20.     return out << "(" << a.x << ", " << a.y << ")";
  21. }
  22.  
  23. template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
  24.     out << "[";
  25.     forn(i, sz(v)) {
  26.         if(i) out << ", ";
  27.         out << v[i];
  28.     }
  29.     return out << "]";
  30. }
  31.  
  32. mt19937 rnd(time(NULL));
  33.  
  34. const int INF = int(1e9);
  35. const li INF64 = li(1e18);
  36. const int MOD = INF + 7;
  37. const ld EPS = 1e-9;
  38. const ld PI = acos(-1.0);
  39.  
  40. const int N = 100 * 1000 + 13;
  41.  
  42. int n;
  43. int a[N];
  44.  
  45. bool read() {
  46.     if (scanf("%d", &n) != 1)
  47.         return false;
  48.     forn(i, n)
  49.         scanf("%d", &a[i]);
  50.     return true;
  51. }
  52.  
  53. li dp[N][4];
  54. int p[N][4];
  55.  
  56. void solve() {
  57.     forn(i, n) forn(j, 4) dp[i][j] = INF64;
  58.     dp[0][2] = a[0];
  59.     if (a[0] > a[1]){
  60.         dp[1][1] = a[0] - a[1];
  61.         p[1][1] = 2;
  62.     }
  63.     if (a[0] < a[1]){
  64.         dp[1][2] = -a[0] + a[1];
  65.         p[1][2] = 0;
  66.     }
  67.     dp[1][3] = a[0] + a[1];
  68.     p[1][3] = 2;
  69.    
  70.     fore(i, 2, n){
  71.         forn(mask, 4){
  72.             forn(j, 2){
  73.                 int nmask = (mask >> 1) + (j << 1);
  74.                 li p2 = (mask & 1 ? a[i - 2] : -a[i - 2]);
  75.                 li p1 = (mask & 2 ? a[i - 1] : -a[i - 1]);
  76.                 li p0 = (j ? a[i] : -a[i]);
  77.                 if (p0 + p1 > 0 && p0 + p1 + p2 > 0 && dp[i - 1][mask] + p0 < dp[i][nmask]){
  78.                     dp[i][nmask] = dp[i - 1][mask] + p0;
  79.                     p[i][nmask] = mask;
  80.                 }
  81.             }
  82.         }
  83.     }
  84.    
  85.     int st = 0;
  86.     forn(i, 4) if (dp[n - 1][i] < dp[n - 1][st]) st = i;
  87.     vector<int> ans;
  88.     for (int i = n - 1; i >= 0; --i){
  89.         ans.pb(st & 2 ? a[i] : -a[i]);
  90.         st = p[i][st];
  91.     }
  92.     reverse(all(ans));
  93.     forn(i, n)
  94.         printf("%d ", ans[i]);
  95.     puts("");
  96. }
  97.  
  98. int main() {
  99. #ifdef _DEBUG
  100.     freopen("input.txt", "r", stdin);
  101. //  freopen("output.txt", "w", stdout);
  102.  
  103.     int tt = clock();
  104.  
  105. #endif
  106.  
  107.     cerr.precision(15);
  108.     cout.precision(15);
  109.     cerr << fixed;
  110.     cout << fixed;
  111.  
  112.     int tc;
  113.     scanf("%d", &tc);
  114.     while (tc--){
  115.         read();
  116.         solve();
  117.  
  118. #ifdef _DEBUG
  119.     cerr << "TIME = " << clock() - tt << endl;
  120.     tt = clock();
  121. #endif
  122.  
  123.     }
  124. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top