Iamtui1010

twosum

Nov 10th, 2021
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. //#include<bits/stdc++.h>
  2. #include<iostream>
  3. #include<fstream>
  4. #include<vector>
  5. #include<unordered_map>
  6. #include<algorithm>
  7.  
  8. #define long int
  9. #define nln '\n'
  10.  
  11. const long N = 1e5;
  12.  
  13. using namespace std;
  14.  
  15. // Global variables: f1, f2, n, a
  16.  
  17. fstream f1, f2;
  18.  
  19. inline void openf()
  20. {
  21.     f1.open("twosum.inp", ios:: in);
  22.     f2.open("twosum.out", ios:: out);
  23. }
  24.  
  25. inline void closef()
  26. {
  27.     f1.close();
  28.     f2.close();
  29. }
  30.  
  31. long n;
  32. vector<long> a, sum;
  33.  
  34. void data()
  35. {
  36.     f1.tie(0)->sync_with_stdio(0);
  37.     f2.tie(0)->sync_with_stdio(0);
  38.     //cin.tie(0)->sync_with_stdio(0);
  39.     cin >> n;
  40.     a.resize(n+2, 0);
  41.     sum.resize(n+2, 0);
  42.     for (long i = 1; i-1 != n; ++i)
  43.     {
  44.         cin >> a[i];
  45.         sum[i] = a[i] + sum[i-1];
  46.     }
  47. }
  48.  
  49. long total(long i, long j)
  50. {
  51.     return sum[j] - sum[i-1];
  52. }
  53.  
  54. template<typename T>
  55. void chmax(T &a, T b) {
  56.   if (a < b) a = b;
  57. }
  58.  
  59. long ans = 0;
  60.  
  61. void process()
  62. {
  63.     unordered_map<long, long> tic;
  64.     tic[0] = 0;
  65.  
  66.     for (long i = 1; i <= n; i++)
  67.     {
  68.         for (long j = i+1; j <= n; j++)
  69.         {
  70.             long tol = sum[j]-sum[i];
  71.             if (tic.count(sum[i]-tol))
  72.                 ans = max(ans, j-tic[sum[i]-tol]);
  73.         }
  74.         tic[sum[i]] = i;
  75.     }
  76. }
  77.  
  78. void view()
  79. {
  80.     cout << ans << nln;
  81. }
  82.  
  83. int main()
  84. {
  85.     openf();
  86.     data();
  87.     process();
  88.     view();
  89.     closef();
  90.     return 0;
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment