Submission #61568


Source Code Expand

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int n = ni();
		int o = 1005;
		int oo = o*2+1;
		long[][] imos0 = new long[oo][oo];
		long[][] imos1 = new long[oo][oo];
		long[][] imos2 = new long[oo][oo];
		for(int i = 0;i < n;i++){
			int type = ni();
			int cx = ni(), cy = ni(), size = ni();
			size--;
			if(type == 1){
				for(int dx = -size;dx <= size;dx++){
					int ly = dx <= 0 ? -size-dx : -size;
					int hy = dx <= 0 ? size : size-dx;
					imos0[cx+dx+o][cy+ly+o]++;
					imos0[cx+dx+o][cy+hy+1+o]--;
				}
			}else if(type == 2){
				for(int dx = -size;dx <= size;dx++){
					int lly = dx <= 0 ? -size-dx : -size;
					int lhy = dx <= 0 ? 0 : -dx;
					int hly = dx <= 0 ? -dx : 0;
					int hhy = dx <= 0 ? size : size-dx;
					imos1[cx+dx+o][cy+lly+o]++;
					imos1[cx+dx+o][cy+lhy+1+o]--;
					imos1[cx+dx+o][cy+hly+1+o]--;
					imos1[cx+dx+o][cy+hhy+2+o]++;
				}
			}else if(type == 3){
				for(int dx = -size;dx <= size;dx++){
					int lly = dx <= 0 ? -size-dx : -size;
					int lhy = dx <= 0 ? 0 : -dx;
					int hhy = dx <= 0 ? size : size-dx;
					imos2[cx+dx+o][cy+lly+o]++;
					imos2[cx+dx+o][cy+lly+1+o]++;
					imos2[cx+dx+o][cy+hhy+2+o]--;
					imos2[cx+dx+o][cy+hhy+3+o]--;
					
					imos2[cx+dx+o][cy+lhy+1+o]-=2*(size-Math.abs(dx))+3;
					imos2[cx+dx+o][cy+lhy+2+o]+=2*(size-Math.abs(dx))+1;
					imos2[cx+dx+o][cy+lhy+Math.abs(dx)+1+o]-=2*(size-Math.abs(dx))+1;
					imos2[cx+dx+o][cy+lhy+Math.abs(dx)+2+o]+=2*(size-Math.abs(dx))+3;
				}
			}
		}
		
		doImos(imos2);
		add(imos1, imos2);
		
		doImos(imos1);
		add(imos0, imos1);
		doImos(imos0);
		
		long max = 0;
		for(int i = 0;i < oo;i++){
			for(int j = 1;j < oo;j++){
				max = Math.max(max, imos0[i][j]);
			}
		}
		out.println(max);
	}
	
	static void doImos(long[][] imos)
	{
		for(int i = 0;i < imos.length;i++){
			for(int j = 1;j < imos[0].length;j++){
				imos[i][j] += imos[i][j-1];
			}
		}
	}
	
	static void add(long[][] dst, long[][] src)
	{
		for(int i = 0;i < dst.length;i++){
			for(int j = 0;j < dst[i].length;j++){
				dst[i][j] += src[i][j];
			}
		}
	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	static boolean eof()
	{
		try {
			is.mark(1000);
			int b;
			while((b = is.read()) != -1 && !(b >= 33 && b <= 126));
			is.reset();
			return b == -1;
		} catch (IOException e) {
			return true;
		}
	}
		
	static int ni()
	{
		try {
			int num = 0;
			boolean minus = false;
			while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
			if(num == '-'){
				num = 0;
				minus = true;
			}else{
				num -= '0';
			}
			
			while(true){
				int b = is.read();
				if(b >= '0' && b <= '9'){
					num = num * 10 + (b - '0');
				}else{
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}
	
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

Submission Info

Submission Time
Task I - その味は甘くて
User uwi
Language Java (OpenJDK 1.7.0)
Score 150
Code Size 3491 Byte
Status AC
Exec Time 1516 ms
Memory 133732 KB

Judge Result

Set Name small large1 large3
Score / Max Score 10 / 10 40 / 40 100 / 100
Status
AC × 20
AC × 39
AC × 63
Set Name Test Cases
small small/case_000.txt, small/case_001.txt, small/case_002.txt, small/case_003.txt, small/case_004.txt, small/case_005.txt, small/case_006.txt, small/case_007.txt, small/case_008.txt, small/case_009.txt, small/case_010.txt, small/case_011.txt, small/case_012.txt, small/case_013.txt, small/case_014.txt, small/case_015.txt, small/case_024.txt, small/case_025.txt, small/case_026.txt, small/case_027.txt
large1 large1/case_000.txt, large1/case_001.txt, large1/case_002.txt, large1/case_003.txt, large1/case_004.txt, large1/case_005.txt, large1/case_006.txt, large1/case_007.txt, large1/case_008.txt, large1/case_009.txt, large1/case_010.txt, large1/case_011.txt, large1/case_012.txt, large1/case_013.txt, large1/case_014.txt, large1/case_015.txt, large1/case_024.txt, large1/case_025.txt, large1/case_026.txt, large1/case_027.txt, large1/large1_case_000.txt, large1/large1_case_001.txt, large1/large1_case_002.txt, large1/large1_case_003.txt, large1/large1_case_004.txt, large1/large1_case_005.txt, large1/large1_case_006.txt, large1/large1_case_007.txt, large1/large1_case_008.txt, large1/large1_case_009.txt, large1/large1_case_010.txt, large1/large1_case_011.txt, large1/large1_case_012.txt, large1/large1_case_013.txt, large1/large1_case_014.txt, large1/large1_case_020.txt, large1/large1_case_021.txt, large1/large1_case_022.txt, large1/large1_case_023.txt
large3 large3/case_000.txt, large3/case_001.txt, large3/case_002.txt, large3/case_003.txt, large3/case_004.txt, large3/case_005.txt, large3/case_006.txt, large3/case_007.txt, large3/case_008.txt, large3/case_009.txt, large3/case_010.txt, large3/case_011.txt, large3/case_012.txt, large3/case_013.txt, large3/case_014.txt, large3/case_015.txt, large3/case_024.txt, large3/case_025.txt, large3/case_026.txt, large3/case_027.txt, large3/large1_case_000.txt, large3/large1_case_001.txt, large3/large1_case_002.txt, large3/large1_case_003.txt, large3/large1_case_004.txt, large3/large1_case_005.txt, large3/large1_case_006.txt, large3/large1_case_007.txt, large3/large1_case_008.txt, large3/large1_case_009.txt, large3/large1_case_010.txt, large3/large1_case_011.txt, large3/large1_case_012.txt, large3/large1_case_013.txt, large3/large1_case_014.txt, large3/large1_case_020.txt, large3/large1_case_021.txt, large3/large1_case_022.txt, large3/large1_case_023.txt, large3/large3_case_000.txt, large3/large3_case_001.txt, large3/large3_case_002.txt, large3/large3_case_003.txt, large3/large3_case_004.txt, large3/large3_case_005.txt, large3/large3_case_006.txt, large3/large3_case_007.txt, large3/large3_case_008.txt, large3/large3_case_009.txt, large3/large3_case_010.txt, large3/large3_case_011.txt, large3/large3_case_012.txt, large3/large3_case_013.txt, large3/large3_case_014.txt, large3/large3_case_015.txt, large3/large3_case_016.txt, large3/large3_case_017.txt, large3/large3_case_018.txt, large3/large3_case_019.txt, large3/large3_case_020.txt, large3/large3_case_021.txt, large3/large3_case_022.txt, large3/large3_case_023.txt
Case Name Status Exec Time Memory
large1/case_000.txt AC 763 ms 129172 KB
large1/case_001.txt AC 766 ms 129504 KB
large1/case_002.txt AC 745 ms 129468 KB
large1/case_003.txt AC 786 ms 129516 KB
large1/case_004.txt AC 769 ms 129260 KB
large1/case_005.txt AC 782 ms 129512 KB
large1/case_006.txt AC 749 ms 129196 KB
large1/case_007.txt AC 791 ms 129460 KB
large1/case_008.txt AC 750 ms 129628 KB
large1/case_009.txt AC 752 ms 129564 KB
large1/case_010.txt AC 769 ms 129632 KB
large1/case_011.txt AC 745 ms 129648 KB
large1/case_012.txt AC 749 ms 129248 KB
large1/case_013.txt AC 763 ms 129204 KB
large1/case_014.txt AC 756 ms 129696 KB
large1/case_015.txt AC 742 ms 129644 KB
large1/case_024.txt AC 734 ms 129196 KB
large1/case_025.txt AC 760 ms 129600 KB
large1/case_026.txt AC 794 ms 129588 KB
large1/case_027.txt AC 740 ms 129460 KB
large1/large1_case_000.txt AC 1162 ms 131612 KB
large1/large1_case_001.txt AC 1133 ms 131952 KB
large1/large1_case_002.txt AC 1287 ms 131948 KB
large1/large1_case_003.txt AC 1103 ms 131548 KB
large1/large1_case_004.txt AC 1183 ms 131580 KB
large1/large1_case_005.txt AC 1107 ms 131948 KB
large1/large1_case_006.txt AC 1083 ms 131688 KB
large1/large1_case_007.txt AC 1141 ms 131920 KB
large1/large1_case_008.txt AC 1158 ms 132072 KB
large1/large1_case_009.txt AC 1099 ms 131196 KB
large1/large1_case_010.txt AC 1145 ms 131940 KB
large1/large1_case_011.txt AC 1103 ms 131988 KB
large1/large1_case_012.txt AC 1113 ms 131948 KB
large1/large1_case_013.txt AC 1139 ms 131720 KB
large1/large1_case_014.txt AC 1078 ms 131984 KB
large1/large1_case_020.txt AC 971 ms 131564 KB
large1/large1_case_021.txt AC 1005 ms 131684 KB
large1/large1_case_022.txt AC 991 ms 131688 KB
large1/large1_case_023.txt AC 1017 ms 131172 KB
large3/case_000.txt AC 751 ms 129192 KB
large3/case_001.txt AC 733 ms 129588 KB
large3/case_002.txt AC 737 ms 129200 KB
large3/case_003.txt AC 742 ms 129188 KB
large3/case_004.txt AC 764 ms 129196 KB
large3/case_005.txt AC 750 ms 129576 KB
large3/case_006.txt AC 776 ms 129204 KB
large3/case_007.txt AC 753 ms 129596 KB
large3/case_008.txt AC 750 ms 129536 KB
large3/case_009.txt AC 757 ms 129508 KB
large3/case_010.txt AC 750 ms 129584 KB
large3/case_011.txt AC 745 ms 129208 KB
large3/case_012.txt AC 754 ms 129136 KB
large3/case_013.txt AC 743 ms 129580 KB
large3/case_014.txt AC 742 ms 129580 KB
large3/case_015.txt AC 743 ms 129204 KB
large3/case_024.txt AC 758 ms 129588 KB
large3/case_025.txt AC 750 ms 129464 KB
large3/case_026.txt AC 758 ms 129664 KB
large3/case_027.txt AC 759 ms 129588 KB
large3/large1_case_000.txt AC 1147 ms 132080 KB
large3/large1_case_001.txt AC 1168 ms 131636 KB
large3/large1_case_002.txt AC 1091 ms 131952 KB
large3/large1_case_003.txt AC 1163 ms 131920 KB
large3/large1_case_004.txt AC 1173 ms 131940 KB
large3/large1_case_005.txt AC 1148 ms 131972 KB
large3/large1_case_006.txt AC 1175 ms 131916 KB
large3/large1_case_007.txt AC 1114 ms 131552 KB
large3/large1_case_008.txt AC 1117 ms 131676 KB
large3/large1_case_009.txt AC 1096 ms 132052 KB
large3/large1_case_010.txt AC 1068 ms 131976 KB
large3/large1_case_011.txt AC 1131 ms 131944 KB
large3/large1_case_012.txt AC 1175 ms 132072 KB
large3/large1_case_013.txt AC 1155 ms 131940 KB
large3/large1_case_014.txt AC 1146 ms 132016 KB
large3/large1_case_020.txt AC 992 ms 132072 KB
large3/large1_case_021.txt AC 1017 ms 132072 KB
large3/large1_case_022.txt AC 1008 ms 131560 KB
large3/large1_case_023.txt AC 963 ms 131932 KB
large3/large3_case_000.txt AC 1509 ms 130748 KB
large3/large3_case_001.txt AC 1441 ms 133732 KB
large3/large3_case_002.txt AC 1470 ms 132820 KB
large3/large3_case_003.txt AC 1449 ms 130980 KB
large3/large3_case_004.txt AC 1496 ms 132340 KB
large3/large3_case_005.txt AC 1445 ms 132360 KB
large3/large3_case_006.txt AC 1516 ms 133300 KB
large3/large3_case_007.txt AC 1385 ms 133284 KB
large3/large3_case_008.txt AC 1390 ms 131824 KB
large3/large3_case_009.txt AC 1444 ms 132828 KB
large3/large3_case_010.txt AC 1469 ms 132984 KB
large3/large3_case_011.txt AC 1402 ms 132500 KB
large3/large3_case_012.txt AC 1485 ms 132144 KB
large3/large3_case_013.txt AC 1463 ms 132872 KB
large3/large3_case_014.txt AC 1439 ms 133356 KB
large3/large3_case_015.txt AC 1379 ms 132664 KB
large3/large3_case_016.txt AC 1333 ms 132388 KB
large3/large3_case_017.txt AC 1441 ms 133300 KB
large3/large3_case_018.txt AC 1338 ms 130788 KB
large3/large3_case_019.txt AC 1412 ms 132124 KB
large3/large3_case_020.txt AC 1225 ms 130736 KB
large3/large3_case_021.txt AC 1249 ms 131100 KB
large3/large3_case_022.txt AC 1361 ms 130876 KB
large3/large3_case_023.txt AC 1272 ms 130876 KB
small/case_000.txt AC 739 ms 129456 KB
small/case_001.txt AC 757 ms 129588 KB
small/case_002.txt AC 744 ms 129592 KB
small/case_003.txt AC 758 ms 129328 KB
small/case_004.txt AC 786 ms 129192 KB
small/case_005.txt AC 751 ms 129184 KB
small/case_006.txt AC 747 ms 129208 KB
small/case_007.txt AC 753 ms 129508 KB
small/case_008.txt AC 750 ms 129328 KB
small/case_009.txt AC 753 ms 129584 KB
small/case_010.txt AC 746 ms 129588 KB
small/case_011.txt AC 769 ms 129588 KB
small/case_012.txt AC 755 ms 129592 KB
small/case_013.txt AC 754 ms 129304 KB
small/case_014.txt AC 749 ms 129248 KB
small/case_015.txt AC 755 ms 129564 KB
small/case_024.txt AC 747 ms 129680 KB
small/case_025.txt AC 754 ms 129208 KB
small/case_026.txt AC 768 ms 129580 KB
small/case_027.txt AC 761 ms 129204 KB