SHARE
TWEET

Java solution for problem D

ahmed_aly Apr 13th, 2011 210 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.InputStreamReader;
  4. import java.io.OutputStreamWriter;
  5. import java.io.PrintWriter;
  6. import java.util.Scanner;
  7.  
  8. public class big_maximum_sum_ahmed_java_ac {
  9.         static int n, m;
  10.         static long[] gen = new long[50], lft = new long[50], rght = new long[50],
  11.                         tot = new long[50];
  12.  
  13.         public static void main(String[] args) {
  14.                 BufferedReader bfin = new BufferedReader(new InputStreamReader(
  15.                                 System.in));
  16.                 BufferedWriter bfout = new BufferedWriter(new OutputStreamWriter(
  17.                                 System.out));
  18.                 Scanner cin = new Scanner(bfin);
  19.                 PrintWriter cout = new PrintWriter(bfout);
  20.                 n = cin.nextInt();
  21.                 m = cin.nextInt();
  22.                 int len, num;
  23.                 for (int i = 0; i < n; i++) {
  24.                         len = cin.nextInt();
  25.                         int mx = -(1 << 30);
  26.                         int sum = 0;
  27.                         for (int j = 0; j < len; j++) {
  28.                                 num = cin.nextInt();
  29.                                 tot[i] += num;
  30.                                 lft[i] = Math.max(lft[i], tot[i]);
  31.                                 rght[i] = Math.min(rght[i], tot[i]);
  32.                                 mx = Math.max(mx, num);
  33.                                 sum += num;
  34.                                 if (sum < 0)
  35.                                         sum = 0;
  36.                                 else
  37.                                         mx = Math.max(mx, sum);
  38.                         }
  39.                         gen[i] = mx;
  40.                         rght[i] = tot[i] - rght[i];
  41.                 }
  42.                 long cur = 0;
  43.                 long best = (long) (-1e18);
  44.                 while (m-- > 0) {
  45.                         int i;
  46.                         i = cin.nextInt();
  47.                         i--;
  48.                         best = Math.max(best, gen[i]);
  49.                         if (cur > 0)
  50.                                 best = Math.max(best, cur + lft[i]);
  51.                         cur = Math.max(0, Math.max(rght[i], cur + tot[i]));
  52.                 }
  53.                 System.out.println(best);
  54.                 cout.close();
  55.         }
  56. }
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