fork download
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace ProgrammingContest.Codeforces.Round33
  7. {
  8. class C
  9. {
  10. static int ReadInt()
  11. {
  12. return int.Parse(Console.ReadLine());
  13. }
  14.  
  15. static int[] ReadInts(int offset = 0)
  16. {
  17. return Console.ReadLine()
  18. .Split(' ')
  19. .Select(s => int.Parse(s) + offset)
  20. .ToArray();
  21. }
  22.  
  23. static int solve(int n, int[] seq)
  24. {
  25. // xs[i,j]: j個のsum
  26. int[,] xs = new int[2,n+1];
  27.  
  28. int[] u = new int[n+1], v = new int[n+1];
  29. int[] idx1 = new int[n + 1], idx2 = new int[n + 1];
  30. // ys[i] - ys[j]: sum [j+1,i]
  31. int[] ys = new int[n+1];
  32. for (int i = 0; i < n; i++) ys[i+1] = ys[i] + seq[i];
  33. for (int i = 0; i < n; i++)
  34. {
  35. xs[0, i + 1] = xs[0, i] - seq[i];
  36. xs[1, i + 1] = xs[1, i] - seq[n - 1 - i];
  37. u[i+1] = Math.Max(xs[0, i + 1], u[i]);
  38. v[i+1] = Math.Max(xs[1, i + 1], v[i]);
  39. idx1[i + 1] = idx1[i];
  40. idx2[i+1] = idx2[i];
  41.  
  42. if (u[i] < xs[0, i + 1]) idx1[i + 1] = i + 1;
  43. if (v[i] < xs[1, i + 1]) idx2[i + 1] = i + 1;
  44. //Console.WriteLine(idx2[i + 1]);
  45. }
  46.  
  47. // u[0] + v[n] + [idx1,idx2]
  48. // -(-4) + (3 - -4) + 0
  49. int res = int.MinValue;
  50. for (int i = 0; i <= n; i++)
  51. {
  52. res = Math.Max(res, u[i] + ys[n-idx2[n -i]] - ys[idx1[i]] + v[n-i]);
  53. //Console.WriteLine("{0}({1}) - {2}({3})", ys[n - idx2[n - i]], n - idx2[n-i], ys[idx1[i]], idx1[i]);
  54. //Console.WriteLine("u: {0}, v: {1}", u[i], v[n-i]);
  55. }
  56. return res;
  57. }
  58.  
  59. public static void Mai()
  60. {
  61. int n = ReadInt();
  62. int[] seq = ReadInts();
  63. Console.WriteLine(solve(n,seq));
  64. }
  65. }
  66. }
  67.  
Not running #stdin #stdout 0s 0KB
stdin
Standard input is empty
stdout

Standard output is empty