Submission #617040


Source Code Expand

using System;
using System.Linq;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using System.Numerics;
using Number = System.Int64;

namespace Program
{
    public class Solver
    {
        public void Solve()
        {
            var h = sc.Integer();
            var w = sc.Integer();
            var map = Enumerate(h, x => sc.Long(w));
            var map2 = Enumerate(w, x => new long[h]);
            for (int i = 0; i < h; i++)
                for (int j = 0; j < w; j++)
                    map2[j][i] = map[i][j];
            foreach(var x in map2)
                Debug.WriteLine(x.AsJoinedString());
            var u = solve(map, h, w);
            var v = solve(map2, w, h);
            IO.Printer.Out.WriteLine(Math.Max(u, v));
        }
        public long solve(long[][] map, int h, int w)
        {
            var cum = createCumulativeSum(map);
            var maU = new long[h];
            var maL = new long[h];
            for (int i = 0; i < h; i++)
                maU[i] = maL[i] = -1L << 60;
        
            for (int i = 0; i < h; i++)
            {
                for (int j = i; j < h; j++)
                {
                    var val = new long[w];
                    for (int k = 0; k < w; k++)
                        val[k] = getArea(cum, i, k, j + 1, k + 1);
                    
                    var max = -1L << 60;
                    for (int k = 0; k < w; k++)
                        max = Math.Max(max, val[k]);

                    long v = 0;
                    for (int k = 0; k < w;)
                    {
                        while (k < w && val[k] + v >= 0)
                        {
                            v += val[k];
                            max = Math.Max(max, v);
                            k++;
                        }
                        if (k < w && val[k] + v < 0)
                        {
                            v = 0;
                            k++;
                        }
                    }
                    maU[i] = Math.Max(maU[i], max);
                    maL[j] = Math.Max(maL[j], max);
                }
            }
            for (int i = h - 1; i > 0; i--)
            {
                maU[i - 1] = Math.Max(maU[i - 1], maU[i]);
            }
            for (int i = 0; i < h - 1; i++)
            {
                maL[i + 1] = Math.Max(maL[i + 1], maL[i]);
            }
            var ans = -1L << 60;
            for (int i = 1; i < h; i++)
            {
                ans = Math.Max(ans, maU[i] + maL[i - 1]);
            }
            return ans;
        }
        #region 累積和
        static public Func<long[][], long[][]> createCumulativeSum = s =>
        {
            int n = s.Length, m = s[0].Length;
            var a = new long[n + 1][];
            for (int i = 0; i <= n; i++)
                a[i] = new long[m + 1];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    a[i + 1][j + 1] = a[i + 1][j] + a[i][j + 1] - a[i][j] + s[i][j];
            return a;
        };
        /// <summary>元のテーブルにおける[x1,x2),[y1,y2)の矩形領域に含まれる値の和を取ってくる</summary>
        static public Func<long[][], int, int, int, int, long> getArea = (a, x1, y1, x2, y2) =>
        {
            if (x1 >= x2 || y1 >= y2) throw new ArgumentException("x1<x2 && y1<y2");
            return a[x2][y2] - a[x1][y2] - a[x2][y1] + a[x1][y1];
        };
        #endregion
        public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
        static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
        static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }

    }
}

#region main
static class Ex
{
    static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); }
    static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
    static public void Main()
    {
        var solver = new Program.Solver();
        solver.Solve();
        Program.IO.Printer.Out.Flush();
    }
}
#endregion
#region Ex
namespace Program.IO
{
    using System.IO;
    using System.Text;
    using System.Globalization;
    public class Printer : StreamWriter
    {
        static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; }
        public static Printer Out { get; set; }
        public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
        public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
        public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
        public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); }
        public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); }
    }
    public class StreamScanner
    {
        public StreamScanner(Stream stream) { str = stream; }
        public readonly Stream str;
        private readonly byte[] buf = new byte[1024];
        private int len, ptr;
        public bool isEof = false;
        public bool IsEndOfStream { get { return isEof; } }
        private byte read()
        {
            if (isEof) return 0;
            if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } }
            return buf[ptr++];
        }
        public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; }

        public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }
        public string ScanLine()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b != '\n'; b = (char)read())
                if (b == 0) break;
                else if (b != '\r') sb.Append(b);
            return sb.ToString();
        }
        public long Long()
        {
            if (isEof) return long.MinValue;
            long ret = 0; byte b = 0; var ng = false;
            do b = read();
            while (b != 0 && b != '-' && (b < '0' || '9' < b));
            if (b == 0) return long.MinValue;
            if (b == '-') { ng = true; b = read(); }
            for (; true; b = read())
            {
                if (b < '0' || '9' < b)
                    return ng ? -ret : ret;
                else ret = ret * 10 + b - '0';
            }
        }
        public int Integer() { return (isEof) ? int.MinValue : (int)Long(); }
        public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; }
        private T[] enumerate<T>(int n, Func<T> f)
        {
            var a = new T[n];
            for (int i = 0; i < n; ++i) a[i] = f();
            return a;
        }

        public char[] Char(int n) { return enumerate(n, Char); }
        public string[] Scan(int n) { return enumerate(n, Scan); }
        public double[] Double(int n) { return enumerate(n, Double); }
        public int[] Integer(int n) { return enumerate(n, Integer); }
        public long[] Long(int n) { return enumerate(n, Long); }
    }
}
#endregion

Submission Info

Submission Time
Task D - 庭園
User camypaper
Language C# (Mono 3.2.1.0)
Score 100
Code Size 7773 Byte
Status AC
Exec Time 937 ms
Memory 16112 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
AC × 4
AC × 15
AC × 30
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask1 subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
sample0.txt AC 117 ms 9008 KB
sample1.txt AC 114 ms 9000 KB
sample2.txt AC 117 ms 8880 KB
sample3.txt AC 113 ms 9012 KB
subtask0_0.txt AC 123 ms 9904 KB
subtask0_1.txt AC 123 ms 9940 KB
subtask0_10.txt AC 123 ms 10032 KB
subtask0_11.txt AC 121 ms 9780 KB
subtask0_12.txt AC 119 ms 10036 KB
subtask0_13.txt AC 120 ms 9904 KB
subtask0_14.txt AC 118 ms 9908 KB
subtask0_2.txt AC 128 ms 9648 KB
subtask0_3.txt AC 121 ms 9824 KB
subtask0_4.txt AC 119 ms 9904 KB
subtask0_5.txt AC 118 ms 9904 KB
subtask0_6.txt AC 120 ms 9908 KB
subtask0_7.txt AC 123 ms 9932 KB
subtask0_8.txt AC 159 ms 9776 KB
subtask0_9.txt AC 119 ms 10008 KB
subtask1_0.txt AC 763 ms 15652 KB
subtask1_1.txt AC 811 ms 16048 KB
subtask1_10.txt AC 725 ms 15868 KB
subtask1_11.txt AC 859 ms 16044 KB
subtask1_12.txt AC 740 ms 16004 KB
subtask1_13.txt AC 937 ms 16112 KB
subtask1_14.txt AC 733 ms 15904 KB
subtask1_2.txt AC 830 ms 16080 KB
subtask1_3.txt AC 715 ms 15936 KB
subtask1_4.txt AC 760 ms 15972 KB
subtask1_5.txt AC 923 ms 16084 KB
subtask1_6.txt AC 783 ms 16052 KB
subtask1_7.txt AC 740 ms 16000 KB
subtask1_8.txt AC 912 ms 16112 KB
subtask1_9.txt AC 763 ms 16080 KB