fork(2) download
copy 
  1. import java.io.InputStreamReader;
  2. import java.io.IOException;
  3. import java.io.BufferedReader;
  4. import java.io.OutputStream;
  5. import java.io.PrintWriter;
  6. import java.util.TreeSet;
  7. import java.util.StringTokenizer;
  8. import java.io.InputStream;
  9.  
  10. /**
  11.  * Built using CHelper plug-in
  12.  * Actual solution is at the top
  13.  * @author Rubanenko
  14.  */
  15. public class Main {
  16. 	public static void main(String[] args) {
  17. 		InputStream inputStream = System.in;
  18. 		OutputStream outputStream = System.out;
  19. 		InputReader in = new InputReader(inputStream);
  20. 		PrintWriter out = new PrintWriter(outputStream);
  21. 		TaskB solver = new TaskB();
  22. 		solver.solve(1, in, out);
  23. 		out.close();
  24. 	}
  25. }
  26.  
  27. class TaskB {
  28.     public void solve(int testNumber, InputReader in, PrintWriter out) {
  29.         int n = in.nextInt();
  30.         int m = in.nextInt();
  31.         int k = in.nextInt();
  32.         long p = in.nextLong();
  33.         long[] h = new long[n], v = new long[m];
  34.         for (int i = 0; i < n; i++) {
  35.             for (int j = 0; j < m; j++) {
  36.                 int x = in.nextInt();
  37.                 h[i] += x;
  38.                 v[j] += x;
  39.             }
  40.         }
  41.         long[] a = new long[k + 1], b = new long[k + 1];
  42.         TreeSet<Long> s = new TreeSet<Long>();
  43.         for (int i = 0; i < n; i++) {
  44.             s.add(h[i]);
  45.         }
  46.         for (int i = 0; i < k; i++) {
  47.             a[i] = s.last();
  48.           //  out.println(a[i]);
  49.             s.remove(a[i]);
  50.             s.add(a[i] - p * (long)m);
  51.             if (i > 0) a[i] = a[i - 1] + a[i];
  52.         }
  53.         s.clear();
  54.         long ans = a[k - 1], res = 0;
  55.         for (int i = 0; i < m; i++) {
  56.             s.add(v[i]);
  57.         }
  58.       //  out.println("------");
  59.         for (int i = 0; i < k; i++) {
  60.             b[i] = s.last();
  61.         //    out.println(b[i]);
  62.             s.remove(b[i]);
  63.             s.add(b[i] - p * (long)n);
  64.             res = res + b[i];
  65.             if (k - i - 2 >= 0) {
  66.                 ans = Math.max(ans, res + a[k - i - 2] - p * ((long)(k - i - 1)) * ((long)(i + 1)));
  67.             }
  68.             //out.println(ans);
  69.         }
  70.         ans = Math.max(ans, res);
  71.         out.println(ans);
  72.     }
  73. }
  74.  
  75. class InputReader {
  76.     private BufferedReader reader;
  77.     private StringTokenizer tokenizer;
  78.  
  79.     public InputReader(InputStream inputStream) {
  80.         reader = new BufferedReader(new InputStreamReader(inputStream));
  81.     }
  82.  
  83.     public String nextLine() {
  84.         String line = null;
  85.         try {
  86.             line = reader.readLine();
  87.         } catch (IOException e) {
  88.             throw new RuntimeException(e);
  89.         }
  90.         return line;
  91.     }
  92.  
  93.     public String next() {
  94.         while (tokenizer == null || !tokenizer.hasMoreTokens())
  95.             tokenizer = new StringTokenizer(nextLine());
  96.         return tokenizer.nextToken();
  97.     }
  98.  
  99.     public int nextInt() {
  100.         return Integer.parseInt(next());
  101.     }
  102.     public long nextLong() {
  103.         return Long.parseLong(next());
  104.     }
  105. }
Runtime error #stdin #stdout #stderr 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.NullPointerException
	at java.util.StringTokenizer.<init>(StringTokenizer.java:199)
	at java.util.StringTokenizer.<init>(StringTokenizer.java:236)
	at InputReader.next(Main.java:95)
	at InputReader.nextInt(Main.java:100)
	at TaskB.solve(Main.java:29)
	at Main.main(Main.java:22)
https://ideone.com/lYV9Wd
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

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!