Submission #2012691

---

Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		if(K == 1){
			Console.WriteLine(A.Max());
			return;
		}
		long[][] dp = new long[K+1][];
		for(int i=0;i<=K;i++){
			dp[i] = new long[N];
		}
		
		for(int i=0;i<N;i++) dp[0][i] = A[i];
		
		for(int t=0;t<K-1;t++){
			var deq = new Deque<int>();
			deq.AddLast(t);
			for(int i=t+1;i<N;i++){
				dp[t+1][i] = (t + 2) * A[i] + dp[t][deq.First];
				while(deq.Count > 0 && dp[t][i] >= dp[t][deq.Last]) deq.RemoveLast();
				deq.AddLast(i);
				if(deq.First < i - M + 1) deq.RemoveFirst();
			}
		}
		
		long ans = 0;
		for(int i=K-1;i<N;i++) ans = Math.Max(ans,dp[K-1][i]);
		Console.WriteLine(ans);
		
	}
	int N, M, K;
	long[] A;
	public Sol(){
		var d = ria();
		N = d[0]; M = d[1]; K = d[2];
		A = rla();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


class Deque<T> :IEnumerable<T>{
	
	
	T[] arr;
	int head, tail;
	int count;
	int capacity;
	
	public int Capacity{
		get{ return capacity;}
		private set{ capacity = value;}
	}
	public int Count{
		get{ return count;}
		private set{ capacity = value;}
	}
	
	public T First {
		get { 
			if(count == 0) throw new Exception("empty");
			return arr[head];
		}
	}
	public T Last {
		get { 
			if(count == 0) throw new Exception("empty");
			return arr[tail]; 
		}
	}
	
	public T this [int pos]{
		get{
			if(pos >= count) throw new ArgumentOutOfRangeException("out of range");
			return arr[(head + pos) % arr.Length];
		}
	}
	
	public IEnumerator<T> GetEnumerator(){
		for(int i=0;i<count;i++){
			yield return arr[(head + i) % arr.Length];
		}
	}
	
	
	IEnumerator IEnumerable.GetEnumerator() {
		return this.GetEnumerator();
	}
		
	public void AddFirst(T elem){
		if(count == capacity) {
			Twice();
		}
		
		head = count == 0 ? head : (head - 1);
		if(head < 0) head = arr.Length - 1;
		arr[head] = elem;
		count++;
		
	}
	
	public void RemoveFirst(){
		if(count == 0) throw new Exception("empty");
		arr[head] = default(T);
		count--;
		head = count == 0 ? head : head + 1; if(head == arr.Length) head = 0;
	}
	
	public void AddLast(T elem){
		if(count == capacity) {
			Twice();
		}
		
		tail = count == 0 ? tail : (tail + 1);
		if(tail >= arr.Length) tail = 0;
		arr[tail] = elem;
		count++;
		
	}
	
	public void RemoveLast(){
		if(count == 0) throw new Exception("empty");
		arr[tail] = default(T);
		count--;
		tail = count == 0 ? tail : tail - 1; if(tail < 0) tail = arr.Length - 1;
	}
	
	void Twice(){
		
		T[] nxt = new T[arr.Length * 2];
		int nhead = arr.Length / 2;
		for(int i = 0; i < count; i++) nxt[nhead + i] = arr[(head + i) % arr.Length];
		head = nhead;
		tail = head + count - 1;
		arr = nxt; 
		capacity = arr.Length;
	}
	
	
	
	public Deque() {
		Init(256);
	}
	
	public Deque(int cap_){
		Init(cap_);
	}
	
	void Init(int cap){
		if(cap < 0) cap = 256;
		arr = new T[cap];
		capacity = cap;
		head = cap / 2;
		tail = cap / 2;
		count = 0;
	}
	
	
}

Submission Info

Judge Result