Advertisement
Anwar_Rizk

Untitled

Oct 1st, 2022
837
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/tree_policy.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #pragma GCC target("fpmath=387") //Turns on excess precision
  5.  
  6. using namespace std;
  7. using namespace __gnu_pbds;
  8.  
  9. #define EPS 1e-9
  10. #define PI acos(-1)
  11. #define ll long long
  12. #define Mod 1'000'000'007
  13. #define INF 2'000'000'000
  14. #define sz(x) int(x.size())
  15. #define all(s) s.begin(), s.end()
  16. #define rall(s) s.rbegin(), s.rend()
  17. #define Num_of_Digits(n) ((int)log10(n)+1)
  18. #define to_decimal(bin) stoll(bin, nullptr, 2)
  19. #define fixed(n) cout << fixed << setprecision(n)
  20. //#define ceil(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))
  21. #define cout(st) for(auto& i : st) cout << i << " "; cout << "\n"
  22. #define cout_map(mp) for(auto& [f, s] : mp) cout << f << " : " << s << "\n"
  23. #define matrix(grid, n, m) vector < vector <int> > grid(n, vector <int> (m));
  24. #define cout_2d(grid) for(auto& v : grid){for(auto& x : v) cout << x << " "; cout << "\n";}
  25. #define cin_2d(grid, n, m) for(int i=0; i<n; i++) for(int j=0; j<m && cin >> grid[i][j]; j++);
  26. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
  27. #define multi_ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
  28.  
  29. template < typename T = int > using Pair = pair < T, T >; //Pair<int> p;
  30.  
  31. template < typename T = int > istream& operator >> (istream &in, vector < T > &v) {
  32.     for (auto &x: v) in >> x;
  33.     return in;
  34. }
  35. template < typename T = int > ostream& operator << (ostream &out, const vector < T > &v) {
  36.     for (const T &x: v) out << x << ' ';
  37.     return out;
  38. }
  39.  
  40. void Anwar_Rizk(){
  41.   ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  42.   #ifndef ONLINE_JUDGE
  43.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  44.   #endif
  45. }
  46.  
  47. // 8 1 4
  48. //-10 15 -11 -5 8 -5 2 2
  49. void max_sum_subarray(vector<ll> arr, int L, int R){
  50.     int n = arr.size();
  51.     vector < ll > pre(n, arr[0]);
  52.     for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + arr[i];
  53.     cout << pre << "\n";
  54.     multiset < ll > s1;
  55.     s1.insert(0);
  56.     ll ans = pre[L - 1];
  57.     int flag = 0;
  58.     for (int i = L; i < n; i++) {
  59.         if (i - R >= 0) {
  60.             if (flag == 0) {
  61.                 auto it = s1.find(0);
  62.                 s1.erase(it);
  63.                 flag = 1;
  64.             }
  65.         }
  66.         cout << "i = " << i << "\n";
  67.         cout << "ans = " << ans << "\n";
  68.         cout << "s1 = ";cout(s1); cout << "----------------\n";
  69.         if (i - L >= 0) s1.insert(pre[i - L]);
  70.         cout(s1); cout << "----------------\n";
  71.         ans = max(ans, pre[i] - *s1.begin());
  72.         if (i - R >= 0) {
  73.             auto it = s1.find(pre[i - R]);
  74.             s1.erase(it);
  75.         }
  76.         cout << "ans = " << ans << "\n";
  77.         cout << "s1 = ";cout(s1); cout << "\n";
  78.     }
  79.     cout << ans << endl;
  80. }
  81.  
  82.  
  83. void solve(){
  84.     ll n, a, b;
  85.     cin >> n >> a >> b;
  86.     vector < ll > v(n);
  87.     cin >> v;
  88.     max_sum_subarray(v, a, b);
  89. }
  90.  
  91. int main()
  92. {   Anwar_Rizk();
  93.  
  94.     int t = 1;
  95.     //cin >> t;
  96.     while(t--){
  97.         solve();
  98.     }
  99.  
  100.   return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement