fork download 
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		InputStream input;
		OutputStream output;
		try {
			input = new FileInputStream("input.txt");
			output = new FileOutputStream("output.txt");
		} catch (FileNotFoundException e) {
			input = System.in;
			output = System.out;
		}
		Kattio io = new Kattio(input, output);
		//int t=io.getInt();
		//for (int i=1; i<=t; i++)
		(new Solve(io)).main();
		io.close();

		if (input instanceof FileInputStream)
			try {
				input.close();
			} catch (IOException e) {
			}
		if (output instanceof FileOutputStream)
			try {
				output.close();
			} catch (IOException e) {
			}
	}
}

class RMQ
{
	int n;
	int[] arr;
	int[] l,r;
	int[] dat;
	int[] pos;
	
	public RMQ(int n)
	{
		this.n = n;
		arr = new int[n+1];
		dat = new int[4*n+1];
		l = new int[4*n+1];
		r = new int[4*n+1];
		pos = new int[n+1];
		RMQHelper(1,1,n);
	}
	
	private void RMQHelper(int i,int x,int y)
	{
		l[i]=x;
		r[i]=y;
		if (x==y)
		{
			dat[i]=arr[x];
			pos[x]=i;
		}
		else
		{
			int m=(x+y)/2;
			RMQHelper(i*2,x,m);
			RMQHelper(i*2+1,m+1,y);
			dat[i]=Math.max(dat[i*2], dat[i*2+1]);
		}
	}
	
	public void update(int x,int y)
	{
		arr[x] = y;
		dat[pos[x]] = y;
		updateHelper(pos[x]/2);
	}
	
	private void updateHelper(int x)
	{
		if (x==0) return;
		
		dat[x] = Math.max(dat[x*2],dat[x*2+1]);
		updateHelper(x/2);
	}
	
	public int get(int l,int r)
	{
		return getHelper(1,l,r);
	}
	
	private int getHelper(int i,int x,int y)
	{
		int res;
		if (y<l[i] || x>r[i]) res=0;
		else
		if (x<=l[i] && r[i]<=y) res=dat[i];
		else
		{
			res=getHelper(i*2,x,y);
			res=Math.max(res,getHelper(i*2+1,x,y));
		}
		
		return res;
	}

	@Override
	public String toString() {
		return "RMQ [n=" + n + ", arr=" + Arrays.toString(arr) + ", l=" + Arrays.toString(l) + ", r="
				+ Arrays.toString(r) + ", dat=" + Arrays.toString(dat) + ", pos=" + Arrays.toString(pos) + "]";
	}
	
	
}

class Solve {
	Kattio io;
	int n,m,k;
	int[][] a;
	RMQ[] ds;
	Solve(Kattio io) {
		this.io = io;
	}
	
	boolean check(int l,int r)
	{
		if (r>n) return false;
		int sum = 0;
		for (int i=1; i<=m; i++)
			sum+=ds[i].get(l, r);
		return (sum<=k);
	}

	void main() {
		n=io.getInt();
		m=io.getInt();
		k=io.getInt();
		a = new int[n+1][m+1];
		for (int i=1; i<=n; i++)
			for (int j=1; j<=m; j++)
				a[i][j]=io.getInt();
		
		ds = new RMQ[m+1];
		
		for (int i=1; i<=m; i++)
		{
			ds[i] = new RMQ(n);
			for (int j=1; j<=n; j++)
				ds[i].update(j, a[j][i]);
		}
		
		//for (int i=1; i<=m; i++)
		//	io.println(ds[i]);
		
		int res = 0;
		int vtres = 0;
		for (int i=1; i<=n; i++)
		{
			int dau = i, cuoi = n;
			do
			{
				int giua=(dau+cuoi)/2;
				if (check(i,giua)) dau=giua+1;
				else cuoi=giua-1;
			}
			while (dau<=cuoi);
			
			if (cuoi-i+1>res)
			{
				res=cuoi-i+1;
				vtres=i;
			}
		}
		
		for (int i=1; i<=m; i++)
			io.print(ds[i].get(vtres,vtres+res-1)+" ");
		
	}
}

class Kattio extends PrintWriter {
	public Kattio(InputStream i) {
		super(new BufferedOutputStream(System.out));
		r = new BufferedReader(new InputStreamReader(i));
	}

	public Kattio(InputStream i, OutputStream o) {
		super(new BufferedOutputStream(o));
		r = new BufferedReader(new InputStreamReader(i));
	}

	public boolean hasMoreTokens() {
		return peekToken() != null;
	}

	public int getInt() {
		return Integer.parseInt(nextToken());
	}

	public double getDouble() {
		return Double.parseDouble(nextToken());
	}

	public long getLong() {
		return Long.parseLong(nextToken());
	}

	public String getWord() {
		return nextToken();
	}

	private BufferedReader r;
	private String line;
	private StringTokenizer st;
	private String token;

	private String peekToken() {
		if (token == null)
			try {
				while (st == null || !st.hasMoreTokens()) {
					line = r.readLine();
					if (line == null)
						return null;
					st = new StringTokenizer(line);
				}
				token = st.nextToken();
			} catch (IOException e) {
			}
		return token;
	}

	private String nextToken() {
		String ans = peekToken();
		token = null;
		return ans;
	}
}
Runtime error #stdin #stdout #stderr 0.05s 2184192KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Exception in thread "main" java.lang.NumberFormatException: null
	at java.lang.Integer.parseInt(Integer.java:542)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Kattio.getInt(Main.java:206)
	at Solve.main(Main.java:144)
	at Main.main(Main.java:28)
https://ideone.com/BDqlhk
language:
Java (HotSpot 12)
created:
5 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!