fork download
copy 
  1. // version1
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. int n, k;
  7.  
  8. long long c1, c2;
  9.  
  10. long long con[1000007];
  11.  
  12. long long res;
  13.  
  14. long long aktual;
  15.  
  16. vector <long long> pos[5];
  17.  
  18. queue <long long> val[5];
  19. int w;
  20.  
  21. long long p;
  22.  
  23. inline long long calc(long long a, long long b)
  24. {
  25.     return ((b-a)%5)*c2+((b-a)/5)*c1;
  26. }
  27.  
  28. int main()
  29. {
  30.     res=1000000000;
  31.     res*=res;
  32.     scanf("%d%d", &n, &k);
  33.     scanf("%lld%lld", &c1, &c2);
  34.     c1=min(c1, 5*c2);
  35.     for (int i=1; i<=n; i++)
  36.     {
  37.         scanf("%lld", &con[i]);
  38.         con[i]+=1000000001;
  39.     }
  40.     sort(con+1, con+n+1);
  41.     for (int i=k; i<=n; i++)
  42.     {
  43.         for (int j=0; j<5; j++)
  44.         {
  45.             pos[(con[i]+j)%5].push_back(con[i]+j);
  46.         }
  47.     }
  48.     for (int h=0; h<5; h++)
  49.     {
  50.         sort(pos[h].begin(), pos[h].end());
  51.         for (int i=0; i<5; i++)
  52.         {
  53.             while(!val[i].empty())
  54.             val[i].pop();
  55.         }
  56.         w=0;
  57.         aktual=0;
  58.         for (int i=0; i<pos[h].size(); i++)
  59.         {
  60.             if (i)
  61.             aktual+=c1*min(w, k)*(pos[h][i]-pos[h][i-1])/5;
  62.             while(w<n && con[w+1]<=pos[h][i])
  63.             {
  64.                 w++;
  65.                 val[con[w]%5].push(con[w]);
  66.                 aktual+=calc(con[w], pos[h][i]);
  67.                 if (w>k)
  68.                 {
  69.                     p=0;
  70.                     for (int j=0; j<5; j++)
  71.                     {
  72.                         if (!val[j].empty())
  73.                         {
  74.                             p=max(p, calc(val[j].front(), pos[h][i]));
  75.                         }
  76.                     }
  77.                     for (int j=0; j<5; j++)
  78.                     {
  79.                         if (!val[j].empty() && calc(val[j].front(), pos[h][i])==p)
  80.                         {
  81.                             aktual-=p;
  82.                             val[j].pop();
  83.                             break;
  84.                         }
  85.                     }
  86.                 }
  87.             }
  88.             if (w>=k)
  89.             {
  90.                 res=min(res, aktual);
  91.             }
  92.         }
  93.     }
  94.     printf("%lld\n", res);
  95.     return 0;
  96. }
  97.  
  98.  
  99. //version2
  100. import java.io.*;
  101. import java.util.*;
  102.  
  103. public class E_bm_ac {
  104. 	FastScanner in;
  105. 	PrintWriter out;
  106.  
  107. 	long plus1, plus5;
  108.  
  109. 	void solve() {
  110. 		int n = in.nextInt();
  111. 		int k = in.nextInt();
  112. 		plus5 = in.nextInt();
  113. 		plus1 = in.nextInt();
  114. 		plus5 = Math.min(plus5, plus1 * 5);
  115. 		int[] t = new int[n];
  116. 		for (int i = 0; i < n; i++) {
  117. 			t[i] = in.nextInt();
  118. 		}
  119. 		Arrays.sort(t);
  120. 		long result = Long.MAX_VALUE;
  121. 		for (int mod5 = 0; mod5 < 5; mod5++) {
  122. 			PriorityQueue<Integer> pq = new PriorityQueue<Integer>(10,
  123. 					new Comparator<Integer>() {
  124. 						@Override
  125. 						public int compare(Integer o1, Integer o2) {
  126. 							long c1 = getCost(o1);
  127. 							long c2 = getCost(o2);
  128. 							return -Long.compare(c1, c2);
  129. 						}
  130. 					});
  131. 			lastValue = Integer.MIN_VALUE;
  132. 			long curCost = 0;
  133. 			for (int i = 0; i < n; i++) {
  134. 				int nextValue = t[i];
  135. 				while (((nextValue % 5) + 5) % 5 != mod5) {
  136. 					nextValue++;
  137. 				}
  138. 				curCost += pq.size() * 1L * ((nextValue - lastValue) / 5) * plus5;
  139. 				lastValue = nextValue;
  140. 				pq.add(t[i]);
  141. 				curCost += getCost(t[i]);
  142. 				if (pq.size() > k) {
  143. 					Integer rem = pq.poll();
  144. 					curCost -= getCost(rem);
  145. 				}
  146. 				if (pq.size() == k && curCost < result) {
  147. 					result = curCost;
  148. 				}
  149. 			}
  150. 		}
  151. 		out.println(result);
  152. 	}
  153.  
  154. 	int lastValue;
  155.  
  156. 	long getCost(long from) {
  157. 		long d = lastValue - from;
  158. 		return (d % 5) * plus1 + (d / 5) * plus5;
  159. 	}
  160.  
  161. 	void run() {
  162. 		try {
  163. 			in = new FastScanner(new File("E.in"));
  164. 			out = new PrintWriter(new File("E.out"));
  165.  
  166. 			solve();
  167.  
  168. 			out.close();
  169. 		} catch (FileNotFoundException e) {
  170. 			e.printStackTrace();
  171. 		}
  172. 	}
  173.  
  174. 	void runIO() {
  175.  
  176. 		in = new FastScanner(System.in);
  177. 		out = new PrintWriter(System.out);
  178.  
  179. 		solve();
  180.  
  181. 		out.close();
  182. 	}
  183.  
  184. 	class FastScanner {
  185. 		BufferedReader br;
  186. 		StringTokenizer st;
  187.  
  188. 		public FastScanner(File f) {
  189. 			try {
  190. 				br = new BufferedReader(new FileReader(f));
  191. 			} catch (FileNotFoundException e) {
  192. 				e.printStackTrace();
  193. 			}
  194. 		}
  195.  
  196. 		public FastScanner(InputStream f) {
  197. 			br = new BufferedReader(new InputStreamReader(f));
  198. 		}
  199.  
  200. 		String next() {
  201. 			while (st == null || !st.hasMoreTokens()) {
  202. 				String s = null;
  203. 				try {
  204. 					s = br.readLine();
  205. 				} catch (IOException e) {
  206. 					e.printStackTrace();
  207. 				}
  208. 				if (s == null)
  209. 					return null;
  210. 				st = new StringTokenizer(s);
  211. 			}
  212. 			return st.nextToken();
  213. 		}
  214.  
  215. 		boolean hasMoreTokens() {
  216. 			while (st == null || !st.hasMoreTokens()) {
  217. 				String s = null;
  218. 				try {
  219. 					s = br.readLine();
  220. 				} catch (IOException e) {
  221. 					e.printStackTrace();
  222. 				}
  223. 				if (s == null)
  224. 					return false;
  225. 				st = new StringTokenizer(s);
  226. 			}
  227. 			return true;
  228. 		}
  229.  
  230. 		int nextInt() {
  231. 			return Integer.parseInt(next());
  232. 		}
  233.  
  234. 		long nextLong() {
  235. 			return Long.parseLong(next());
  236. 		}
  237.  
  238. 		double nextDouble() {
  239. 			return Double.parseDouble(next());
  240. 		}
  241. 	}
  242.  
  243. 	public static void main(String[] args) {
  244. 		new E_bm_ac().runIO();
  245. 	}
  246. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:124:7: error: stray '@' in program
       @Override
       ^
prog.cpp:100:1: error: 'import' does not name a type
 import java.io.*;
 ^
prog.cpp:101:1: error: 'import' does not name a type
 import java.util.*;
 ^
prog.cpp:103:1: error: expected unqualified-id before 'public'
 public class E_bm_ac {
 ^
stdout
copy 
Standard output is empty
https://ideone.com/FkE3DU
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!