SHARE
TWEET

C++ solution for problem D

ahmed_aly Apr 13th, 2011 619 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstring>
  2. #include <map>
  3. #include <deque>
  4. #include <queue>
  5. #include <stack>
  6. #include <sstream>
  7. #include <iostream>
  8. #include <iomanip>
  9. #include <cstdio>
  10. #include <cmath>
  11. #include <cstdlib>
  12. #include <ctime>
  13. #include <algorithm>
  14. #include <vector>
  15. #include <set>
  16. #include <complex>
  17. #include <list>
  18. #include <climits>
  19. #include <cctype>
  20.  
  21. using namespace std;
  22.  
  23. int n, m;
  24.  
  25. long long gen[50], lft[50], rght[50], tot[50];
  26.  
  27. int main() {
  28.         scanf("%d%d", &n, &m);
  29.         int len, num;
  30.         for (int i = 0; i < n; i++) {
  31.                 scanf("%d", &len);
  32.                 int mx = -(1 << 30);
  33.                 int sum = 0;
  34.                 for (int j = 0; j < len; j++) {
  35.                         scanf("%d", &num);
  36.                         tot[i] += num;
  37.                         lft[i] = max(lft[i], tot[i]);
  38.                         rght[i] = min(rght[i], tot[i]);
  39.                         mx = max(mx, num);
  40.                         sum += num;
  41.                         if (sum < 0)
  42.                                 sum = 0;
  43.                         else
  44.                                 mx = max(mx, sum);
  45.                 }
  46.                 gen[i] = mx;
  47.                 rght[i] = tot[i] - rght[i];
  48.         }
  49.         long long cur = 0;
  50.         long long best = (long long) (-1e18);
  51.         while (m--) {
  52.                 int i;
  53.                 scanf("%d", &i);
  54.                 i--;
  55.                 best = max(best, gen[i]);
  56.                 if (cur)
  57.                         best = max(best, cur + lft[i]);
  58.                 cur = max(0ll, max(rght[i], cur + tot[i]));
  59.         }
  60.         cout << best << endl;
  61.         return 0;
  62. }
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