結果

問題 No.2139 K Consecutive Sushi
ユーザー yuimyoyuimyo
提出日時 2022-12-09 06:08:37
言語 C#
(.NET 8.0.203)
結果
WA  
実行時間 -
コード長 14,317 bytes
コンパイル時間 13,274 ms
コンパイル使用メモリ 166,868 KB
実行使用メモリ 202,700 KB
最終ジャッジ日時 2024-10-14 18:33:33
合計ジャッジ時間 17,717 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
28,032 KB
testcase_01 AC 53 ms
28,160 KB
testcase_02 AC 54 ms
28,032 KB
testcase_03 AC 210 ms
40,192 KB
testcase_04 AC 211 ms
40,320 KB
testcase_05 AC 209 ms
40,448 KB
testcase_06 AC 211 ms
40,372 KB
testcase_07 AC 210 ms
40,192 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 54 ms
28,032 KB
testcase_14 AC 54 ms
27,904 KB
testcase_15 AC 54 ms
28,032 KB
testcase_16 AC 54 ms
28,112 KB
testcase_17 AC 54 ms
28,160 KB
testcase_18 AC 56 ms
28,160 KB
testcase_19 AC 55 ms
27,904 KB
testcase_20 AC 55 ms
28,160 KB
testcase_21 WA -
testcase_22 AC 57 ms
28,032 KB
testcase_23 WA -
testcase_24 AC 112 ms
33,280 KB
testcase_25 WA -
testcase_26 AC 81 ms
31,616 KB
testcase_27 WA -
testcase_28 AC 107 ms
33,152 KB
testcase_29 AC 86 ms
31,616 KB
testcase_30 AC 118 ms
34,432 KB
testcase_31 AC 194 ms
39,100 KB
testcase_32 AC 88 ms
31,744 KB
testcase_33 AC 214 ms
202,700 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (96 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using AtCoder;
using AtCoder.Internal;
using Kzrnm.Competitive.IO;
using System;
using System.Buffers.Text;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Runtime.CompilerServices;
using System.Text;
namespace AdventCalendarContest2022.Problems
{
    internal partial class ProblemC
    {
        static void Solve()
        {
            var N = cr.Int();
            var K = cr.Int() - 1;
            var A = cr.Repeat<long>(N);
            var B = new List<(long Value, int Index)>();
            for (int i = 0; i < N; i++)
                B.Add((A[i], i));
            B.Sort((a,b)=>Math.Sign(b.Value-a.Value));
            var C = new bool[N];
            var uf = new DSU(N);
            foreach(var (val, i) in B)
            {
                bool used = false;
                if (i > 0 && C[i - 1] && i < N - 1 && C[i + 1])
                {
                    if (uf.Size(i - 1) + uf.Size(i + 1) < K)
                    {
                        uf.Merge(i - 1, i);
                        uf.Merge(i + 1, i);
                        used = true;
                    }
                }
                else if (i > 0 && C[i - 1])
                {
                    if (uf.Size(i - 1) < K)
                    {
                        uf.Merge(i - 1, i);
                        used = true;
                    }
                }
                else if (i < N - 1 && C[i + 1])
                {
                    if (uf.Size(i + 1) < K)
                    {
                        uf.Merge(i + 1, i);
                        used = true;
                    }
                }
                else
                {
                    used = true;
                }
                C[i] = used;
            }
            var ans = 0L;
            for (int i = 0; i < N; i++)
                if (C[i]) ans += A[i];
            cw.WriteLine(ans);
        }
    }
}

#region Dependency resolution
namespace AdventCalendarContest2022.Problems
{
    internal partial class ProblemC
    {
        static ConsoleReader cr;
        static ConsoleWriter cw;
#if COMPETITIVE
        public ProblemC(string outputFilePath = null, bool solving = true)
#else
        static void Main(string[] args)
#endif
        {
#if COMPETITIVE
            SourceExpander.Expander.Expand(outputFilePath: outputFilePath);
#endif
            if (cw != null)
                cw.Dispose();
            cr = new ConsoleReader();
            cw = new ConsoleWriter();
#if COMPETITIVE
            if (solving)
#endif
                Solve();
            cw.Dispose();
        }
    }
}
#endregion
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace AtCoder{public class DSU{internal readonly int _n;public readonly int[]_parentOrSize;public DSU(int n){_n=n;_parentOrSize=new int[n];_parentOrSize.AsSpan().Fill(-1);}[MethodImpl(256)]public int Merge(int a,int b){int x=Leader(a),y=Leader(b);if(x==y)return x;if(-_parentOrSize[x]<-_parentOrSize[y])(x,y)=(y,x);_parentOrSize[x]+=_parentOrSize[y];_parentOrSize[y]=x;return x;}[MethodImpl(256)]public bool Same(int a,int b){return Leader(a)==Leader(b);}[MethodImpl(256)]public int Leader(int a){if(_parentOrSize[a]<0)return a;while(0<=_parentOrSize[_parentOrSize[a]]){(a,_parentOrSize[a])=(_parentOrSize[a],_parentOrSize[_parentOrSize[a]]);}return _parentOrSize[a];}[MethodImpl(256)]public int Size(int a){return-_parentOrSize[Leader(a)];}[MethodImpl(256)]public int[][]Groups(){int[]leaderBuf=new int[_n];int[]id=new int[_n];var resultList=new SimpleList<int[]>(_n);for(int i=0;i<leaderBuf.Length;i++){leaderBuf[i]=Leader(i);if(i==leaderBuf[i]){id[i]=resultList.Count;resultList.Add(new int[-_parentOrSize[i]]);}}var result=resultList.ToArray();int[]ind=new int[result.Length];for(int i=0;i<leaderBuf.Length;i++){var leaderID=id[leaderBuf[i]];result[leaderID][ind[leaderID]]=i;ind[leaderID]++;}return result;}}}
namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{private T[]data;private const int DefaultCapacity=2;public SimpleList(){data=new T[DefaultCapacity];}public SimpleList(int capacity){data=new T[Math.Max(capacity,DefaultCapacity)];}public SimpleList(IEnumerable<T>collection){if(collection is ICollection<T>col){data=new T[col.Count];col.CopyTo(data,0);Count=col.Count;}else{data=new T[DefaultCapacity];foreach(var item in collection)Add(item);}}[MethodImpl(256)]public Memory<T>AsMemory()=>new Memory<T>(data,0,Count);[MethodImpl(256)]public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[MethodImpl(256)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}[MethodImpl(256)]public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}[MethodImpl(256)]public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}[MethodImpl(256)]public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}[MethodImpl(256)]public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}[MethodImpl(256)]public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}[MethodImpl(256)]public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}[MethodImpl(256)]public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}[MethodImpl(256)]public void Clear()=>Count=0;[MethodImpl(256)]public bool Contains(T item)=>IndexOf(item)>=0;[MethodImpl(256)]public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);[MethodImpl(256)]public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);[MethodImpl(256)]public T[]ToArray()=>AsSpan().ToArray();bool ICollection<T>.IsReadOnly=>false;T IList<T>.this[int index]{get=>data[index];set=>data[index]=value;}T IReadOnlyList<T>.this[int index]{get=>data[index];}void IList<T>.Insert(int index,T item)=>throw new NotSupportedException();bool ICollection<T>.Remove(T item)=>throw new NotSupportedException();void IList<T>.RemoveAt(int index)=>throw new NotSupportedException();IEnumerator IEnumerable.GetEnumerator()=>((IEnumerable<T>)this).GetEnumerator();IEnumerator<T>IEnumerable<T>.GetEnumerator(){for(int i=0;i<Count;i++)yield return data[i];}[MethodImpl(256)]public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}}
namespace Kzrnm.Competitive.IO{using static Utf8Parser;using _R=ConsoleReader;using MI=System.Runtime.CompilerServices.MethodImplAttribute;public class ConsoleReader{internal const int BufSize=1<<12;internal readonly Stream input;internal readonly Encoding encoding;internal readonly byte[]buf;internal int pos;internal int len;[MI(256)]public ConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding,BufSize){}[MI(256)]public ConsoleReader(Stream input,Encoding encoding):this(input,encoding,BufSize){}[MI(256)]public ConsoleReader(Stream input,Encoding encoding,int bufferSize){this.input=input;this.encoding=encoding;buf=new byte[bufferSize];}[MI(256)]private void FillEntireNumber(){if((uint)pos>=(uint)buf.Length)FillNextBuffer();while(buf[pos]<=' ')if( ++pos>=len)FillNextBuffer();if(pos+21>=buf.Length&&buf[buf.Length-1]>' ')FillEntireNumberImpl();}private void FillEntireNumberImpl(){buf.AsSpan(pos,len-pos).CopyTo(buf);len-=pos;pos=0;var numberOfBytes=input.Read(buf,len,buf.Length-len);if(numberOfBytes==0)buf[len++]=10;else if(numberOfBytes+len<buf.Length)buf[buf.Length-1]=10;len+=numberOfBytes;}private void FillNextBuffer(){if((len=input.Read(buf,0,buf.Length))==0){buf[0]=10;len=1;}else if(len<buf.Length)buf[buf.Length-1]=10;pos=0;}[MI(256)]internal byte ReadByte(){if(pos>=len)FillNextBuffer();return buf[pos++];}[MI(256)]public T Read<T>(){if(typeof(T)==typeof(int))return(T)(object)Int();if(typeof(T)==typeof(uint))return(T)(object)UInt();if(typeof(T)==typeof(long))return(T)(object)Long();if(typeof(T)==typeof(ulong))return(T)(object)ULong();if(typeof(T)==typeof(double))return(T)(object)Double();if(typeof(T)==typeof(decimal))return(T)(object)Decimal();if(typeof(T)==typeof(char))return(T)(object)Char();if(typeof(T)==typeof(string))return(T)(object)Ascii();return Throw<T>();}static T Throw<T>()=>throw new NotSupportedException(typeof(T).Name);[MI(256)]public int Int(){FillEntireNumber();TryParse(buf.AsSpan(pos),out int v,out int bc);pos+=bc;return v;}[MI(256)]public uint UInt(){FillEntireNumber();TryParse(buf.AsSpan(pos),out uint v,out int bc);pos+=bc;return v;}[MI(256)]public long Long(){FillEntireNumber();TryParse(buf.AsSpan(pos),out long v,out int bc);pos+=bc;return v;}[MI(256)]public ulong ULong(){FillEntireNumber();TryParse(buf.AsSpan(pos),out ulong v,out int bc);pos+=bc;return v;}[MI(256)]public double Double(){FillEntireNumber();TryParse(buf.AsSpan(pos),out double v,out int bc);pos+=bc;return v;}[MI(256)]public decimal Decimal(){FillEntireNumber();TryParse(buf.AsSpan(pos),out decimal v,out int bc);pos+=bc;return v;}[MI(256)]public string String(){var sb=new List<byte>();;byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(' '<b);return encoding.GetString(sb.ToArray());}[MI(256)]public string Ascii(){var sb=new StringBuilder();byte b;do b=ReadByte();while(b<=' ');do{sb.Append((char)b);b=ReadByte();}while(' '<b);return sb.ToString();}[MI(256)]public string Line(){var sb=new List<byte>();byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}[MI(256)]public char Char(){byte b;do b=ReadByte();while(b<=' ');return(char)b;}[MI(256)]public int Int0()=>Int()-1;[MI(256)]public uint UInt0()=>UInt()-1;[MI(256)]public long Long0()=>Long()-1;[MI(256)]public ulong ULong0()=>ULong()-1;[MI(256)]public static implicit operator int(_R cr)=>cr.Int();[MI(256)]public static implicit operator uint(_R cr)=>cr.UInt();[MI(256)]public static implicit operator long(_R cr)=>cr.Long();[MI(256)]public static implicit operator ulong(_R cr)=>cr.ULong();[MI(256)]public static implicit operator double(_R cr)=>cr.Double();[MI(256)]public static implicit operator decimal(_R cr)=>cr.Decimal();[MI(256)]public static implicit operator string(_R cr)=>cr.Ascii();public T[]Repeat<T>(int count){var arr=new T[count];for(int i=0;i<arr.Length;i++)arr[i]=Read<T>();return arr;}}}
namespace Kzrnm.Competitive.IO{using _W=ConsoleWriter;using MI=System.Runtime.CompilerServices.MethodImplAttribute;public sealed partial class ConsoleWriter:IDisposable{private const int BufSize=1<<12;private readonly StreamWriter sw;public StreamWriter StreamWriter=>sw;public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,BufSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){sw=new StreamWriter(output,encoding,bufferSize);}[MI(256)]public void Flush()=>sw.Flush();[MI(256)]public void Dispose()=>Flush();[MI(256)]public _W Write<T>(T v){sw.Write(v.ToString());return this;}[MI(256)]public _W WriteLine(){sw.WriteLine();return this;}[MI(256)]public _W WriteLine<T>(T v){sw.WriteLine(v.ToString());return this;}[MI(256)]public _W WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);[MI(256)]public _W WriteLineJoin<T1,T2>((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);[MI(256)]public _W WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);[MI(256)]public _W WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);[MI(256)]public _W WriteLineJoin<TTuple>(TTuple tuple)where TTuple:System.Runtime.CompilerServices.ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++)col[i]=tuple[i];return WriteLineJoin(col);}[MI(256)]public _W WriteLineJoin(params object[]col)=>WriteMany(' ',col);[MI(256)]public _W WriteLineJoin<T1,T2>(T1 v1,T2 v2){sw.Write(v1.ToString());sw.Write(' ');sw.WriteLine(v2.ToString());return this;}[MI(256)]public _W WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){sw.Write(v1.ToString());sw.Write(' ');sw.Write(v2.ToString());sw.Write(' ');sw.WriteLine(v3.ToString());return this;}[MI(256)]public _W WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){sw.Write(v1.ToString());sw.Write(' ');sw.Write(v2.ToString());sw.Write(' ');sw.Write(v3.ToString());sw.Write(' ');sw.WriteLine(v4.ToString());return this;}[MI(256)]public _W WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);[MI(256)]public _W WriteGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}[MI(256)]public _W WriteGrid<TTuple>(IEnumerable<TTuple>tuples)where TTuple:System.Runtime.CompilerServices.ITuple{foreach(var tup in tuples)WriteLineJoin(tup);return this;}[MI(256)]private _W WriteMany<T>(char sep,IEnumerable<T>col){var en=col.GetEnumerator();if(!en.MoveNext())goto End;sw.Write(en.Current.ToString());while(en.MoveNext()){sw.Write(sep);sw.Write(en.Current.ToString());}End:sw.WriteLine();return this;}}}
namespace Kzrnm.Competitive.IO{using MI=System.Runtime.CompilerServices.MethodImplAttribute;public partial class ConsoleWriter{[MI(256)]public ConsoleWriter WriteLine(ReadOnlySpan<char>v){sw.WriteLine(v);return this;}[MI(256)]public ConsoleWriter WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);[MI(256)]public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);[MI(256)]public ConsoleWriter WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);[MI(256)]public ConsoleWriter WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);[MI(256)]private ConsoleWriter WriteMany<T>(char sep,ReadOnlySpan<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;sw.Write(en.Current.ToString());while(en.MoveNext()){sw.Write(sep);sw.Write(en.Current.ToString());}sw.WriteLine();return this;}}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander
0