fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/klJej
language:
C# (gmcs 5.20.1)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!