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 R2D2AndDroidArmy {
  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. class RMQEfficient
  124. {
  125. 	int n;
  126. 	int[] arr;
  127. 	int[][] rmq;
  128. 	int[] pow;
  129. 	int[] mn;
  130.  
  131. 	public RMQEfficient(int[] arr)
  132. 	{
  133. 		this.n = arr.length-1;
  134.  
  135. 		this.arr = new int[arr.length];
  136. 		for (int i=1; i<=n; i++)
  137. 			this.arr[i] = arr[i];
  138.  
  139. 		initPowMn();
  140. 		initRMQ();
  141. 	}
  142.  
  143. 	private void initPowMn()
  144. 	{
  145. 		pow = new int[31];
  146. 		pow[0] = 1;
  147.  
  148. 		mn = new int[n+1];
  149. 		Arrays.fill(mn, 0);
  150.  
  151. 		for (int i=1; i<=30; i++)
  152. 		{
  153. 			pow[i]=2*pow[i-1];
  154. 			if (pow[i]<=n) 
  155. 			{
  156. 				try
  157. 				{
  158. 					mn[pow[i]] = i;
  159. 				}
  160. 				catch (IndexOutOfBoundsException e)
  161. 				{
  162. 					System.out.println(n+" "+pow[i]+" "+i);
  163. 				}
  164. 			}
  165. 		}
  166.  
  167. 		for (int i=1; i<=n; i++)
  168. 			mn[i] = Math.max(mn[i-1], mn[i]);
  169. 	}
  170.  
  171. 	private void initRMQ()
  172. 	{
  173. 		rmq = new int[n+1][31];
  174. 		for (int i=1; i<=n; i++)
  175. 			Arrays.fill(rmq[i],-1);
  176. 		for (int i=1; i<=n; i++)
  177. 			for (int j=0; j<=30; j++)
  178. 				initRMQHelper(i,j);
  179. 	}
  180.  
  181. 	private int initRMQHelper(int x,int y)
  182. 	{
  183. 		if (x>n) return 0;
  184. 		else
  185. 		if (rmq[x][y]!=-1) return rmq[x][y];
  186. 		else
  187. 		if (y==0)
  188. 			rmq[x][y]=arr[x];
  189. 		else
  190. 		{
  191. 			int endSide = x+pow[y]-1;
  192. 			rmq[x][y]=Math.max(initRMQHelper(x,y-1),
  193. 					initRMQHelper(endSide-pow[y-1]+1,y-1));
  194. 		}
  195. 		return rmq[x][y];
  196. 	}
  197.  
  198. 	public int get(int l,int r)
  199. 	{
  200. 		if (r<l) return 0;
  201. 		//System.out.println("get "+l+" "+r);
  202. 		int length = (r-l+1);
  203. 		int step = mn[length];
  204. 		//System.out.println(step);
  205. 		try
  206. 		{
  207. 			return Math.max(rmq[l][step],rmq[r-pow[step]+1][step]);
  208. 		}
  209. 		catch (ArrayIndexOutOfBoundsException e)
  210. 		{
  211. 			System.out.println(l+" "+r+" "+(r-pow[step]+1)+" "+step);
  212. 			return 0;
  213. 		}
  214. 	}
  215.  
  216. }
  217.  
  218. class Solve {
  219. 	Kattio io;
  220. 	int n,m,k;
  221. 	int[][] a;
  222. 	RMQEfficient[] ds;
  223. 	Solve(Kattio io) {
  224. 		this.io = io;
  225. 	}
  226.  
  227. 	boolean check(int l,int r)
  228. 	{
  229. 		//io.println("check "+l+" "+r);
  230. 		if (r>n) return false;
  231. 		int sum = 0;
  232. 		for (int i=1; i<=m; i++)
  233. 		{
  234. 			//io.println("check "+l+" "+r);
  235. 			sum+=ds[i].get(l, r);
  236. 		}
  237. 		return (sum<=k);
  238. 	}
  239.  
  240. 	void main() {
  241. 		n=io.getInt();
  242. 		m=io.getInt();
  243. 		k=io.getInt();
  244. 		a = new int[n+1][m+1];
  245. 		for (int i=1; i<=n; i++)
  246. 			for (int j=1; j<=m; j++)
  247. 				a[i][j]=io.getInt();
  248.  
  249. 		ds = new RMQEfficient[m+1];
  250.  
  251. 		for (int i=1; i<=m; i++)
  252. 		{
  253. 			int[] init = new int[n+1];
  254. 			for (int j=1; j<=n; j++)
  255. 				init[j]=a[j][i];
  256. 			ds[i] = new RMQEfficient(init);
  257. 		}
  258.  
  259. 		//for (int i=1; i<=m; i++)
  260. 		//	io.println(ds[i]);
  261.  
  262. 		int res = 0;
  263. 		int vtres = 0;
  264. 		for (int i=1; i<=n; i++)
  265. 		{
  266. 			int dau = i, cuoi = n;
  267. 			do
  268. 			{
  269. 				int giua=(dau+cuoi)/2;
  270. 				if (check(i,giua)) dau=giua+1;
  271. 				else cuoi=giua-1;
  272. 			}
  273. 			while (dau<=cuoi);
  274.  
  275. 			if (cuoi-i+1>res)
  276. 			{
  277. 				res=cuoi-i+1;
  278. 				vtres=i;
  279. 			}
  280. 		}
  281.  
  282. 		for (int i=1; i<=m; i++)
  283. 			io.print(ds[i].get(vtres,vtres+res-1)+" ");
  284.  
  285. 	}
  286. }
  287.  
  288. class Kattio extends PrintWriter {
  289. 	public Kattio(InputStream i) {
  290. 		super(new BufferedOutputStream(System.out));
  291. 		r = new BufferedReader(new InputStreamReader(i));
  292. 	}
  293.  
  294. 	public Kattio(InputStream i, OutputStream o) {
  295. 		super(new BufferedOutputStream(o));
  296. 		r = new BufferedReader(new InputStreamReader(i));
  297. 	}
  298.  
  299. 	public boolean hasMoreTokens() {
  300. 		return peekToken() != null;
  301. 	}
  302.  
  303. 	public int getInt() {
  304. 		return Integer.parseInt(nextToken());
  305. 	}
  306.  
  307. 	public double getDouble() {
  308. 		return Double.parseDouble(nextToken());
  309. 	}
  310.  
  311. 	public long getLong() {
  312. 		return Long.parseLong(nextToken());
  313. 	}
  314.  
  315. 	public String getWord() {
  316. 		return nextToken();
  317. 	}
  318.  
  319. 	private BufferedReader r;
  320. 	private String line;
  321. 	private StringTokenizer st;
  322. 	private String token;
  323.  
  324. 	private String peekToken() {
  325. 		if (token == null)
  326. 			try {
  327. 				while (st == null || !st.hasMoreTokens()) {
  328. 					line = r.readLine();
  329. 					if (line == null)
  330. 						return null;
  331. 					st = new StringTokenizer(line);
  332. 				}
  333. 				token = st.nextToken();
  334. 			} catch (IOException e) {
  335. 			}
  336. 		return token;
  337. 	}
  338.  
  339. 	private String nextToken() {
  340. 		String ans = peekToken();
  341. 		token = null;
  342. 		return ans;
  343. 	}
  344. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/svURnd
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!