Submission #669429

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
669429	2022-12-06T12:06:54 Z	erray	Uplifting Excursion (BOI22_vault)	C++17	Compilation error	0 ms	0 KB

vault

    // author: erray
    #include <bits/stdc++.h>
     
    #ifdef DEBUG
      #include "debug.h"
    #else
      #define debug(...) void(37)
    #endif
     
    using namespace std;
     
    int main() {
      ios_base::sync_with_stdio(false);
      cin.tie(0);
      int M;
      long long L;
      cin >> M >> L;
      vector<long long> neg(M), pos(M);
      long long banked = 0;
      for (int i = 0; i < M; ++i) {
        cin >> neg[M - i - 1];
      }
      cin >> banked;
      for (int i = 0; i < M; ++i) {
        cin >> pos[i];
      }
      const int inf = int(1e9);
      vector<int> dp(M * M + 1, -inf);
      dp[0] = 0;
      auto Push = [&](int x, long long c, int delta) {
        bool rev = false;
        if (x < 0) {
          rev = true;
          x = -x;
          reverse(dp.begin(), dp.end());
        }
        for (int r = 0; r < x; ++r) {
          deque<pair<int, int>> dq;
          for (int i = r, ps = 0; i < int(dp.size()); i += x, ++ps) {
            int push = dp[i] + (ps * -delta);
            while (!dq.empty() && dq.back().first <= push) {
              dq.pop_back();
            }
            dq.emplace_back(push, ps);
            if (ps > c) {
              int rem = ps - c - 1;
              if (dq.front().second == rem) {
                dq.pop_front();
              }
            }
            dp[i] = dq.front().first + (delta * ps);
          } 
        }
        if (rev) {
          reverse(dp.begin(), dp.end());
        }
      };
     
      auto Value = [&](vector<long long> x) {
        long long res = 0;
        for (int i = 0; i < M; ++i) {
          res += (i + 1) * x[i];
        }
        return res;
      };
      if (Value(pos) - Value(neg) < L) {
        swap(pos, neg);
        L = -L;
      }
      debug(L, pos, neg);
      for (int i = 0; i < M; ++i) {
        L += (i + 1) * neg[i]; 
        banked += neg[i];
      }
      vector<long long> dec(M);
      for (int i = 0; i < M; ++i) {
        dec[i] = max(0LL, min(pos[i], L / (i + 1)));
        L -= dec[i] * (i + 1);
        pos[i] -= dec[i];  
        banked += dec[i];
      }
      assert(L >= 0);
      for (int i = 0; i < M; ++i) {
        Push(i + 1, pos[i], +1);
      }
      for (int i = 0; i < M; ++i) {
        Push(i + 1, neg[i], -1);      
      }
      for (int i = 0; i < M; ++i) {
        Push(-(i + 1), dec[i], -1);
      }
      if (L < 0 || dp[L] == -inf) {
        cout << "impossible\n";
      } else {
        cout << banked + dp[L] << '\n';
      }
    }
      dp[0] = 0;
      auto Push = [&](int x, long long c, int delta) {
        bool rev = false;
        if (x < 0) {
          rev = true;
          x = -x;
          reverse(dp.begin(), dp.end());
        }
        for (int r = 0; r < x; ++r) {
          deque<pair<int, int>> dq;
          for (int i = r, ps = 0; i < int(dp.size()); i += x, ++ps) {
            int push = dp[i] + (ps * -delta);
            while (!dq.empty() && dq.back().first <= push) {
              dq.pop_back();
            }
            dq.emplace_back(push, ps);
            if (ps > c) {
              int rem = ps - c - 1;
              if (dq.front().second == rem) {
                dq.pop_front();
              }
            }
            dp[i] = dq.front().first + (delta * ps);
          } 
        }
        if (rev) {
          reverse(dp.begin(), dp.end());
        }
      };
     
      auto Value = [&](vector<long long> x) {
        long long res = 0;
        for (int i = 0; i < M; ++i) {
          res += (i + 1) * x[i];
        }
        return res;
      };
      if (Value(pos) - Value(neg) < L) {
        swap(pos, neg);
        L = -L;
      }
      debug(L, pos, neg);
      for (int i = 0; i < M; ++i) {
        L += (i + 1) * neg[i]; 
        banked += neg[i];
      }
      vector<long long> dec(M);
      for (int i = 0; i < M; ++i) {
        dec[i] = max(0LL, min(pos[i], L / (i + 1));
        L -= dec[i] * (i + 1);
        pos[i] -= dec[i];  
        banked += dec[i];
      }
     
      for (int i = 0; i < M; ++i) {
        Push(i + 1, pos[i], +1);
      }
      for (int i = 0; i < M; ++i) {
        Push(i + 1, neg[i], -1);      
      }
      for (int i = 0; i < M; ++i) {
        Push(-(i + 1), dec[i], -1);
      }
      if (L < 0 || dp[L] == -inf) {
        cout << "impossible\n";
      } else {
        cout << banked + dp[L] << '\n';
      }
    }

Compilation message

vault.cpp:3:5: error: extended character   is not valid in an identifier
    3 |      
      |     ^
vault.cpp:9:5: error: extended character   is not valid in an identifier
    9 |      
      |     ^
vault.cpp:11:5: error: extended character   is not valid in an identifier
   11 |      
      |     ^
vault.cpp:58:5: error: extended character   is not valid in an identifier
   58 |      
      |     ^
vault.cpp:127:5: error: extended character   is not valid in an identifier
  127 |      
      |     ^
vault.cpp:151:5: error: extended character   is not valid in an identifier
  151 |      
      |     ^
vault.cpp:3:5: error: '\U000000a0' does not name a type
    3 |      
      |     ^
vault.cpp:11:5: error: '\U000000a0' does not name a type
   11 |      
      |     ^
vault.cpp:98:7: error: 'dp' does not name a type
   98 |       dp[0] = 0;
      |       ^~
vault.cpp:99:20: error: non-local lambda expression cannot have a capture-default
   99 |       auto Push = [&](int x, long long c, int delta) {
      |                    ^
vault.cpp: In lambda function:
vault.cpp:104:19: error: 'dp' was not declared in this scope
  104 |           reverse(dp.begin(), dp.end());
      |                   ^~
vault.cpp:104:11: error: 'reverse' was not declared in this scope; did you mean 'std::reverse'?
  104 |           reverse(dp.begin(), dp.end());
      |           ^~~~~~~
      |           std::reverse
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from vault.cpp:2:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:249:1: note: 'std::reverse' declared here
  249 | reverse(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last);
      | ^~~~~~~
vault.cpp:107:11: error: 'deque' was not declared in this scope
  107 |           deque<pair<int, int>> dq;
      |           ^~~~~
vault.cpp:107:11: note: suggested alternatives:
In file included from /usr/include/c++/10/deque:67,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:68,
                 from vault.cpp:2:
/usr/include/c++/10/bits/stl_deque.h:764:11: note:   'std::deque'
  764 |     class deque : protected _Deque_base<_Tp, _Alloc>
      |           ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:68,
                 from vault.cpp:2:
/usr/include/c++/10/deque:83:13: note:   'std::pmr::deque'
   83 |       using deque = std::deque<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~
vault.cpp:107:17: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
  107 |           deque<pair<int, int>> dq;
      |                 ^~~~
      |                 std::pair
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from vault.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'std::pair' declared here
  211 |     struct pair
      |            ^~~~
vault.cpp:107:22: error: expected primary-expression before 'int'
  107 |           deque<pair<int, int>> dq;
      |                      ^~~
vault.cpp:108:43: error: 'dp' was not declared in this scope
  108 |           for (int i = r, ps = 0; i < int(dp.size()); i += x, ++ps) {
      |                                           ^~
vault.cpp:110:21: error: 'dq' was not declared in this scope
  110 |             while (!dq.empty() && dq.back().first <= push) {
      |                     ^~
vault.cpp:113:13: error: 'dq' was not declared in this scope
  113 |             dq.emplace_back(push, ps);
      |             ^~
vault.cpp:124:19: error: 'dp' was not declared in this scope
  124 |           reverse(dp.begin(), dp.end());
      |                   ^~
vault.cpp:124:11: error: 'reverse' was not declared in this scope; did you mean 'std::reverse'?
  124 |           reverse(dp.begin(), dp.end());
      |           ^~~~~~~
      |           std::reverse
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from vault.cpp:2:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:249:1: note: 'std::reverse' declared here
  249 | reverse(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last);
      | ^~~~~~~
vault.cpp: At global scope:
vault.cpp:127:5: error: '\U000000a0' does not name a type
  127 |      
      |     ^
vault.cpp:135:7: error: expected unqualified-id before 'if'
  135 |       if (Value(pos) - Value(neg) < L) {
      |       ^~
vault.cpp:7:31: error: expected unqualified-id before numeric constant
    7 |       #define debug(...) void(37)
      |                               ^~
vault.cpp:139:7: note: in expansion of macro 'debug'
  139 |       debug(L, pos, neg);
      |       ^~~~~
vault.cpp:7:31: error: expected ')' before numeric constant
    7 |       #define debug(...) void(37)
      |                              ~^~
vault.cpp:139:7: note: in expansion of macro 'debug'
  139 |       debug(L, pos, neg);
      |       ^~~~~
vault.cpp:140:7: error: expected unqualified-id before 'for'
  140 |       for (int i = 0; i < M; ++i) {
      |       ^~~
vault.cpp:140:23: error: 'i' does not name a type
  140 |       for (int i = 0; i < M; ++i) {
      |                       ^
vault.cpp:140:30: error: expected unqualified-id before '++' token
  140 |       for (int i = 0; i < M; ++i) {
      |                              ^~
vault.cpp:144:7: error: 'vector' does not name a type
  144 |       vector<long long> dec(M);
      |       ^~~~~~
vault.cpp:145:7: error: expected unqualified-id before 'for'
  145 |       for (int i = 0; i < M; ++i) {
      |       ^~~
vault.cpp:145:23: error: 'i' does not name a type
  145 |       for (int i = 0; i < M; ++i) {
      |                       ^
vault.cpp:145:30: error: expected unqualified-id before '++' token
  145 |       for (int i = 0; i < M; ++i) {
      |                              ^~
vault.cpp:151:5: error: '\U000000a0' does not name a type
  151 |      
      |     ^
vault.cpp:152:23: error: 'i' does not name a type
  152 |       for (int i = 0; i < M; ++i) {
      |                       ^
vault.cpp:152:30: error: expected unqualified-id before '++' token
  152 |       for (int i = 0; i < M; ++i) {
      |                              ^~
vault.cpp:155:7: error: expected unqualified-id before 'for'
  155 |       for (int i = 0; i < M; ++i) {
      |       ^~~
vault.cpp:155:23: error: 'i' does not name a type
  155 |       for (int i = 0; i < M; ++i) {
      |                       ^
vault.cpp:155:30: error: expected unqualified-id before '++' token
  155 |       for (int i = 0; i < M; ++i) {
      |                              ^~
vault.cpp:158:7: error: expected unqualified-id before 'for'
  158 |       for (int i = 0; i < M; ++i) {
      |       ^~~
vault.cpp:158:23: error: 'i' does not name a type
  158 |       for (int i = 0; i < M; ++i) {
      |                       ^
vault.cpp:158:30: error: expected unqualified-id before '++' token
  158 |       for (int i = 0; i < M; ++i) {
      |                              ^~
vault.cpp:161:7: error: expected unqualified-id before 'if'
  161 |       if (L < 0 || dp[L] == -inf) {
      |       ^~
vault.cpp:163:9: error: expected unqualified-id before 'else'
  163 |       } else {
      |         ^~~~
vault.cpp:166:5: error: expected declaration before '}' token
  166 |     }
      |     ^