• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
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, lft = new long, rght = new long,
11.                         tot = new long;
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.

Top