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 R2D2AndDroidArmy {
	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 RMQEfficient
{
	int n;
	int[] arr;
	int[][] rmq;
	int[] pow;
	int[] mn;
	
	public RMQEfficient(int[] arr)
	{
		this.n = arr.length-1;
		
		this.arr = new int[arr.length];
		for (int i=1; i<=n; i++)
			this.arr[i] = arr[i];
		
		initPowMn();
		initRMQ();
	}
	
	private void initPowMn()
	{
		pow = new int[31];
		pow[0] = 1;
		
		mn = new int[n+1];
		Arrays.fill(mn, 0);
		
		for (int i=1; i<=30; i++)
		{
			pow[i]=2*pow[i-1];
			if (pow[i]<=n) 
			{
				try
				{
					mn[pow[i]] = i;
				}
				catch (IndexOutOfBoundsException e)
				{
					System.out.println(n+" "+pow[i]+" "+i);
				}
			}
		}
		
		for (int i=1; i<=n; i++)
			mn[i] = Math.max(mn[i-1], mn[i]);
	}
	
	private void initRMQ()
	{
		rmq = new int[n+1][31];
		for (int i=1; i<=n; i++)
			Arrays.fill(rmq[i],-1);
		for (int i=1; i<=n; i++)
			for (int j=0; j<=30; j++)
				initRMQHelper(i,j);
	}
	
	private int initRMQHelper(int x,int y)
	{
		if (x>n) return 0;
		else
		if (rmq[x][y]!=-1) return rmq[x][y];
		else
		if (y==0)
			rmq[x][y]=arr[x];
		else
		{
			int endSide = x+pow[y]-1;
			rmq[x][y]=Math.max(initRMQHelper(x,y-1),
					initRMQHelper(endSide-pow[y-1]+1,y-1));
		}
		return rmq[x][y];
	}
	
	public int get(int l,int r)
	{
		if (r<l) return 0;
		//System.out.println("get "+l+" "+r);
		int length = (r-l+1);
		int step = mn[length];
		//System.out.println(step);
		try
		{
			return Math.max(rmq[l][step],rmq[r-pow[step]+1][step]);
		}
		catch (ArrayIndexOutOfBoundsException e)
		{
			System.out.println(l+" "+r+" "+(r-pow[step]+1)+" "+step);
			return 0;
		}
	}
	
}

class Solve {
	Kattio io;
	int n,m,k;
	int[][] a;
	RMQEfficient[] ds;
	Solve(Kattio io) {
		this.io = io;
	}
	
	boolean check(int l,int r)
	{
		//io.println("check "+l+" "+r);
		if (r>n) return false;
		int sum = 0;
		for (int i=1; i<=m; i++)
		{
			//io.println("check "+l+" "+r);
			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 RMQEfficient[m+1];
		
		for (int i=1; i<=m; i++)
		{
			int[] init = new int[n+1];
			for (int j=1; j<=n; j++)
				init[j]=a[j][i];
			ds[i] = new RMQEfficient(init);
		}
		
		//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;
	}
}
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
Main.java:14: error: class R2D2AndDroidArmy is public, should be declared in a file named R2D2AndDroidArmy.java
public class R2D2AndDroidArmy {
       ^
1 error
stdout 
Standard output is empty
https://ideone.com/svURnd
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!