fork download
copy 
  1. import java.io.BufferedOutputStream;
  2. import java.io.BufferedReader;
  3. import java.io.FileInputStream;
  4. import java.io.FileNotFoundException;
  5. import java.io.FileOutputStream;
  6. import java.io.IOException;
  7. import java.io.InputStream;
  8. import java.io.InputStreamReader;
  9. import java.io.OutputStream;
  10. import java.io.PrintWriter;
  11. import java.util.Arrays;
  12. import java.util.StringTokenizer;
  13.  
  14. public class Main {
  15. 	public static void main(String[] args) {
  16. 		InputStream input;
  17. 		OutputStream output;
  18. 		try {
  19. 			input = new FileInputStream("input.txt");
  20. 			output = new FileOutputStream("output.txt");
  21. 		} catch (FileNotFoundException e) {
  22. 			input = System.in;
  23. 			output = System.out;
  24. 		}
  25. 		Kattio io = new Kattio(input, output);
  26. 		//int t=io.getInt();
  27. 		//for (int i=1; i<=t; i++)
  28. 		(new Solve(io)).main();
  29. 		io.close();
  30.  
  31. 		if (input instanceof FileInputStream)
  32. 			try {
  33. 				input.close();
  34. 			} catch (IOException e) {
  35. 			}
  36. 		if (output instanceof FileOutputStream)
  37. 			try {
  38. 				output.close();
  39. 			} catch (IOException e) {
  40. 			}
  41. 	}
  42. }
  43.  
  44. class RMQ
  45. {
  46. 	int n;
  47. 	int[] arr;
  48. 	int[] l,r;
  49. 	int[] dat;
  50. 	int[] pos;
  51.  
  52. 	public RMQ(int n)
  53. 	{
  54. 		this.n = n;
  55. 		arr = new int[n+1];
  56. 		dat = new int[4*n+1];
  57. 		l = new int[4*n+1];
  58. 		r = new int[4*n+1];
  59. 		pos = new int[n+1];
  60. 		RMQHelper(1,1,n);
  61. 	}
  62.  
  63. 	private void RMQHelper(int i,int x,int y)
  64. 	{
  65. 		l[i]=x;
  66. 		r[i]=y;
  67. 		if (x==y)
  68. 		{
  69. 			dat[i]=arr[x];
  70. 			pos[x]=i;
  71. 		}
  72. 		else
  73. 		{
  74. 			int m=(x+y)/2;
  75. 			RMQHelper(i*2,x,m);
  76. 			RMQHelper(i*2+1,m+1,y);
  77. 			dat[i]=Math.max(dat[i*2], dat[i*2+1]);
  78. 		}
  79. 	}
  80.  
  81. 	public void update(int x,int y)
  82. 	{
  83. 		arr[x] = y;
  84. 		dat[pos[x]] = y;
  85. 		updateHelper(pos[x]/2);
  86. 	}
  87.  
  88. 	private void updateHelper(int x)
  89. 	{
  90. 		if (x==0) return;
  91.  
  92. 		dat[x] = Math.max(dat[x*2],dat[x*2+1]);
  93. 		updateHelper(x/2);
  94. 	}
  95.  
  96. 	public int get(int l,int r)
  97. 	{
  98. 		return getHelper(1,l,r);
  99. 	}
  100.  
  101. 	private int getHelper(int i,int x,int y)
  102. 	{
  103. 		int res;
  104. 		if (y<l[i] || x>r[i]) res=0;
  105. 		else
  106. 		if (x<=l[i] && r[i]<=y) res=dat[i];
  107. 		else
  108. 		{
  109. 			res=getHelper(i*2,x,y);
  110. 			res=Math.max(res,getHelper(i*2+1,x,y));
  111. 		}
  112.  
  113. 		return res;
  114. 	}
  115.  
  116. 	@Override
  117. 	public String toString() {
  118. 		return "RMQ [n=" + n + ", arr=" + Arrays.toString(arr) + ", l=" + Arrays.toString(l) + ", r="
  119. 				+ Arrays.toString(r) + ", dat=" + Arrays.toString(dat) + ", pos=" + Arrays.toString(pos) + "]";
  120. 	}
  121.  
  122.  
  123. }
  124.  
  125. class Solve {
  126. 	Kattio io;
  127. 	int n,m,k;
  128. 	int[][] a;
  129. 	RMQ[] ds;
  130. 	Solve(Kattio io) {
  131. 		this.io = io;
  132. 	}
  133.  
  134. 	boolean check(int l,int r)
  135. 	{
  136. 		if (r>n) return false;
  137. 		int sum = 0;
  138. 		for (int i=1; i<=m; i++)
  139. 			sum+=ds[i].get(l, r);
  140. 		return (sum<=k);
  141. 	}
  142.  
  143. 	void main() {
  144. 		n=io.getInt();
  145. 		m=io.getInt();
  146. 		k=io.getInt();
  147. 		a = new int[n+1][m+1];
  148. 		for (int i=1; i<=n; i++)
  149. 			for (int j=1; j<=m; j++)
  150. 				a[i][j]=io.getInt();
  151.  
  152. 		ds = new RMQ[m+1];
  153.  
  154. 		for (int i=1; i<=m; i++)
  155. 		{
  156. 			ds[i] = new RMQ(n);
  157. 			for (int j=1; j<=n; j++)
  158. 				ds[i].update(j, a[j][i]);
  159. 		}
  160.  
  161. 		//for (int i=1; i<=m; i++)
  162. 		//	io.println(ds[i]);
  163.  
  164. 		int res = 0;
  165. 		int vtres = 0;
  166. 		for (int i=1; i<=n; i++)
  167. 		{
  168. 			int dau = i, cuoi = n;
  169. 			do
  170. 			{
  171. 				int giua=(dau+cuoi)/2;
  172. 				if (check(i,giua)) dau=giua+1;
  173. 				else cuoi=giua-1;
  174. 			}
  175. 			while (dau<=cuoi);
  176.  
  177. 			if (cuoi-i+1>res)
  178. 			{
  179. 				res=cuoi-i+1;
  180. 				vtres=i;
  181. 			}
  182. 		}
  183.  
  184. 		for (int i=1; i<=m; i++)
  185. 			io.print(ds[i].get(vtres,vtres+res-1)+" ");
  186.  
  187. 	}
  188. }
  189.  
  190. class Kattio extends PrintWriter {
  191. 	public Kattio(InputStream i) {
  192. 		super(new BufferedOutputStream(System.out));
  193. 		r = new BufferedReader(new InputStreamReader(i));
  194. 	}
  195.  
  196. 	public Kattio(InputStream i, OutputStream o) {
  197. 		super(new BufferedOutputStream(o));
  198. 		r = new BufferedReader(new InputStreamReader(i));
  199. 	}
  200.  
  201. 	public boolean hasMoreTokens() {
  202. 		return peekToken() != null;
  203. 	}
  204.  
  205. 	public int getInt() {
  206. 		return Integer.parseInt(nextToken());
  207. 	}
  208.  
  209. 	public double getDouble() {
  210. 		return Double.parseDouble(nextToken());
  211. 	}
  212.  
  213. 	public long getLong() {
  214. 		return Long.parseLong(nextToken());
  215. 	}
  216.  
  217. 	public String getWord() {
  218. 		return nextToken();
  219. 	}
  220.  
  221. 	private BufferedReader r;
  222. 	private String line;
  223. 	private StringTokenizer st;
  224. 	private String token;
  225.  
  226. 	private String peekToken() {
  227. 		if (token == null)
  228. 			try {
  229. 				while (st == null || !st.hasMoreTokens()) {
  230. 					line = r.readLine();
  231. 					if (line == null)
  232. 						return null;
  233. 					st = new StringTokenizer(line);
  234. 				}
  235. 				token = st.nextToken();
  236. 			} catch (IOException e) {
  237. 			}
  238. 		return token;
  239. 	}
  240.  
  241. 	private String nextToken() {
  242. 		String ans = peekToken();
  243. 		token = null;
  244. 		return ans;
  245. 	}
  246. }
Runtime error #stdin #stdout #stderr 0.05s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
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:
6 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!