stetsyk

Untitled

Dec 26th, 2014
236
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.50 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <memory.h>
  5. #include <iostream>
  6. #include <string>
  7. #include <cstring>
  8. #include <vector>
  9. #include <cmath>
  10. #include <map>
  11. #include <algorithm>
  12. #include <cstdio>
  13. #include <set>
  14. #include <list>
  15. #include <queue>
  16. #define y1 vamdlsfmvldf
  17. using namespace std;
  18. #define mp make_pair
  19. typedef long long ll;
  20. const ll mod = 1000000009;
  21. const int inf = (int)(1e9 + 7);
  22. const double pi = 3.1415926535897932;
  23. const int N = 500005;
  24. int n;
  25. int t[4 * N];
  26. void build(int a[], int v, int tl, int tr)
  27. {
  28.     if(tl == tr) t[v] = a[tl];
  29.     else
  30.     {
  31.         int md = (tl + tr) / 2;
  32.         build(a, v + v, tl, md);
  33.         build(a, v + v + 1, md + 1, tr);
  34.         t[v] = min(t[v + v], t[v + v + 1]);
  35.     }
  36. }
  37. int query(int v, int tl, int tr, int l, int r)
  38. {
  39.     if(l > r) return inf;
  40.     if(l == tl && r == tr) return t[v];
  41.     int tm = (tl + tr) / 2;
  42.     return min(query(v + v, tl, tm, l, min(r,tm)), query(v + v + 1, tm + 1, tr, max(l,tm+1), r));
  43. }
  44. int qu(int l, int r)
  45. {
  46.     return query(1, 0, n - 1, l, r);
  47. }
  48. int a[N];
  49. int b[5];
  50. int f(){
  51.     int used[5];
  52.     int ans = 0;
  53.     memset(used, 0, sizeof(used));
  54.     for(int i = 0; i < 3; ++i){
  55.         used[b[i]] = 1;
  56.         int ind1 = b[i] - 1;
  57.         int ind2 = b[i] + 1;
  58.         while(ind1 >= 0 && used[ind1] == 1){
  59.             --ind1;
  60.         }
  61.         if(ind1 == -1) return 0;
  62.         while(ind2 < 5 && used[ind2] == 1){
  63.             ++ind2;
  64.         }
  65.         if(ind2 == 5) return 0;
  66.         ans += min(a[ind1], a[ind2]);
  67.     }
  68.     return ans;
  69. }
  70. int main()
  71. {
  72.     int mx = 0;
  73.     ll sum = 0;
  74.     //cin >> n;
  75.     /*if(n <= 2){
  76.         cout << 0 << endl;
  77.         return 0;
  78.     }
  79.     if(n == 3){
  80.         cout << min(a[0], a[2]) << endl;
  81.         return 0;
  82.     }*/
  83.     int n = 5;
  84.     for(int i = 1; i <= 5; ++i)
  85.     {
  86.         a[i - 1] = i;
  87.     }
  88.     do
  89.     {
  90.         int tmp = 0;
  91.         for(int i = 1; i <= 5; ++i){
  92.             b[i - 1] = i - 1;
  93.         }
  94.         do{
  95.             tmp = max(tmp, f());
  96.         }while(next_permutation(b, b + 5));
  97.         //cout << 1 << endl;
  98.         for(int i = 0; i < n; ++i)
  99.         {
  100.             //cin >> a[i];
  101.             mx = max(a[i], mx);
  102.             sum += a[i];
  103.         }
  104.         //if(a[0] == mx || a[1] == mx || a[n - 2] == mx || a[n - 1] == mx) while(true);
  105.         ll ans = 0;
  106.         for(int i = 2; i < n - 2; ++i)
  107.         {
  108.             if(a[i] == mx)
  109.             {
  110.                 ll cur = sum - a[i - 1] - a[i + 1];
  111.                 cur -= mx;
  112.                 cur += min(a[0], a[n - 1]);
  113.                 ans = max(ans, cur);
  114.             }
  115.         }
  116.         if(a[1] == mx)
  117.         {
  118.             ll cur = sum - a[2] - a[1] - a[0];
  119.             cur += min(a[0], a[n - 1]);
  120.             ans = max(ans, cur);
  121.         }
  122.         if(a[n - 2] == mx)
  123.         {
  124.             ll cur = sum -  a[n - 1] - a[n - 2] - a[n - 3];
  125.             cur += min(a[0], a[n - 1]);
  126.             ans = max(ans, cur);
  127.         }
  128.         if(a[0] == mx)
  129.         {
  130.             ll cur = sum - a[0] - a[1];
  131.             ans = max(ans, cur);
  132.         }
  133.         if(a[n - 1] == mx)
  134.         {
  135.             ll cur = sum - a[n - 1] - a[n - 2];
  136.             ans = max(ans, cur);
  137.         }
  138.         //cout << ans << endl;
  139.         if(ans != tmp){
  140.             cout << ans << " " << tmp << endl;
  141.             cout << a[0] << " " << a[1] << " " << a[2] << " " << a[3] << " " << a[4] << endl;
  142.         }
  143.     }
  144.     while(next_permutation(a, a + 5));
  145.     return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment