Submission #2159718


Source Code Expand

using System;
using System.Linq;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using SB = System.Text.StringBuilder;
using Number = System.Int64;
using System.Numerics;
using static System.Math;
namespace Program {
    public class Solver {
        Random rnd = new Random(0);
        public void Solve() {
            var n = ri;

            var a = Enumerate(n, x => new long[] { rl, rl }).ToList();
            if (n % 2 == 0) { n++; a.Add(new long[] { 0, 0 }); }
            a.Sort((l, r) => (l[0] + l[1]).CompareTo(r[0] + r[1]));
            a.Reverse();
            //左側に動かすコスト Σi*Len_{i} + Σr_i
            //右側に動かすコスト Σi*Len_{i} + Σl_i

            //すでに i 個左に置かれていて,中心に置いたかどうか
            var dp = new long[n + 5, 2];
            for (int i = 0; i < n + 5; i++)
                for (int j = 0; j < 2; j++)
                    dp[i, j] = INF;
            dp[0, 0] = 0;
            var cnt = 0;
            foreach (var x in a)
            {
                var l = x[0];
                var r = x[1];
                var len = x[0] + x[1];
                Debug.WriteLine(len);
                var next = new long[n + 5, 2];
                for (int i = 0; i < n + 5; i++)
                    for (int j = 0; j < 2; j++)
                        next[i, j] = INF;
                for (int j = 0; j < 2; j++)
                    for (int i = 0; i + j <= cnt; i++)
                    {
                        var k = cnt - j - i;
                        //left
                        next[i + 1, j] = Math.Min(next[i + 1, j], dp[i, j] + i * len + r);
                        //right
                        next[i, j] = Math.Min(next[i, j], dp[i, j] + k * len + l);
                        //center
                        if (j == 0) next[i, j + 1] = Math.Min(next[i, j + 1], dp[i, j] + len * (n - 1) / 2);

                    }
                cnt++;
                dp = next;
            }
            Console.WriteLine(dp[(n - 1) / 2, 1]);
        }
        const long INF = 1L << 60;
        static int[] dx = { -1, 0, 1, 0 };
        static int[] dy = { 0, 1, 0, -1 };

        int ri { get { return sc.Integer(); } }
        long rl { get { return sc.Long(); } }
        double rd { get { return sc.Double(); } }
        string rs { get { return sc.Scan(); } }
        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(ie.ToArray()); }

    static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") {
        return string.Join(st, ie);
    }

    static public void Main() {
        Console.SetOut(new Program.IO.Printer(Console.OpenStandardOutput()) { AutoFlush = false });
        var solver = new Program.Solver();
        try
        {
            solver.Solve();
            Console.Out.Flush();
        }
        catch { }
    }
}
#endregion
#region Ex
namespace Program.IO {
    using System.IO;
    using System.Text;
    using System.Globalization;

    public class Printer: StreamWriter {
        public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
        public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
    }

    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 != 0; b = (char)read()) if (b != '\r') sb.Append(b);
            return sb.ToString();
        }
        public long Long() { return isEof ? long.MinValue : long.Parse(Scan()); }
        public int Integer() { return isEof ? int.MinValue : int.Parse(Scan()); }
        public double Double() { return isEof ? double.NaN : double.Parse(Scan(), CultureInfo.InvariantCulture); }
    }
}

#endregion

Submission Info

Submission Time
Task F - Intervals
User camypaper
Language C# (Mono 4.6.2.0)
Score 1000
Code Size 5350 Byte
Status AC
Exec Time 911 ms
Memory 30456 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 2
AC × 45
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 908 ms 28400 KB
001.txt AC 186 ms 29272 KB
002.txt AC 909 ms 26360 KB
003.txt AC 686 ms 25960 KB
004.txt AC 892 ms 26376 KB
005.txt AC 351 ms 28016 KB
006.txt AC 886 ms 26360 KB
007.txt AC 454 ms 30448 KB
008.txt AC 901 ms 28416 KB
009.txt AC 105 ms 26192 KB
010.txt AC 893 ms 28400 KB
011.txt AC 385 ms 28492 KB
012.txt AC 897 ms 28408 KB
013.txt AC 92 ms 29792 KB
014.txt AC 888 ms 26360 KB
015.txt AC 186 ms 29144 KB
016.txt AC 911 ms 26352 KB
017.txt AC 663 ms 30128 KB
018.txt AC 889 ms 28424 KB
019.txt AC 423 ms 26840 KB
020.txt AC 24 ms 11220 KB
021.txt AC 24 ms 9300 KB
022.txt AC 911 ms 28400 KB
023.txt AC 908 ms 26376 KB
024.txt AC 901 ms 28408 KB
025.txt AC 891 ms 28400 KB
026.txt AC 904 ms 28416 KB
027.txt AC 898 ms 30448 KB
028.txt AC 900 ms 28416 KB
029.txt AC 891 ms 28400 KB
030.txt AC 890 ms 28400 KB
031.txt AC 889 ms 28408 KB
032.txt AC 889 ms 26368 KB
033.txt AC 890 ms 30456 KB
034.txt AC 891 ms 30456 KB
035.txt AC 889 ms 28408 KB
036.txt AC 887 ms 30456 KB
037.txt AC 890 ms 28400 KB
038.txt AC 890 ms 28424 KB
039.txt AC 903 ms 30456 KB
040.txt AC 896 ms 28408 KB
041.txt AC 904 ms 30456 KB
042.txt AC 908 ms 28400 KB
example0.txt AC 25 ms 11348 KB
example1.txt AC 25 ms 11348 KB