結果
| 問題 |
No.2509 Beam Shateki
|
| コンテスト | |
| ユーザー |
 Asahi
|
| 提出日時 | 2023-10-20 22:58:48 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 20,375 bytes |
| コンパイル時間 | 4,396 ms |
| コンパイル使用メモリ | 95,744 KB |
| 実行使用メモリ | 57,876 KB |
| 最終ジャッジ日時 | 2024-09-20 21:17:44 |
| 合計ジャッジ時間 | 9,319 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | TLE * 1 -- * 60 |
ソースコード
import java.util.*;
import java.io.*;
import java.math.*;
import java.util.stream.*;
import java.util.function.*;
import java.security.SecureRandom;
class Main implements Runnable
{
void solve()
{
int H = in.nextInt() , W = in.nextInt();
long [][] grid = new long[H + 2][W + 2];
for(int i = 1 ; i < H + 1 ; i ++ )
{
for(int j = 1 ; j < W + 1 ; j ++ )
{
grid[i][j] = in.nextLong();
}
}
List<IntPair> position = new ArrayList<>();
for(int i = 0 ; i < H + 2 ; i ++ )
{
for(int j = 0 ; j < W + 2 ; j ++ )
{
if(i == 0 || j == 0 || i == H + 1 || j == W + 1)
{
position.add(new IntPair(i , j));
}
}
}
List<Set<IntPair>> [] P = new ArrayList[position.size()];
for(int i = 0 ; i < position.size() ; i ++ ) P[i] = new ArrayList<>();
for(int i = 0 ; i < position.size() ; i ++ )
{
for(int dir = 0 ; dir < 8 ; dir ++ )
{
int y = position.get(i).fi , x = position.get(i).se ;
int [][] used = new int[H + 2][W + 2];
used[y][x] = 1 ;
HashSet<IntPair> box = new HashSet<>();
y += dy8[dir] ; x += dx8[dir] ;
while(x > 0 && x < W + 1 && y > 0 && y < H + 1)
{
box.add(new IntPair(y , x));
y += dy8[dir] ; x += dx8[dir] ;
}
P[i].add(box);
}
}
long max = 0 ;
for(int i = 0 ; i < position.size() ; i ++ )
{
for(int j = i + 1 ; j < position.size() ; j ++ )
{
for(int k = 0 ; k < 8 ; k ++ )
{
for(int l = 0 ; l < 8 ; l ++ )
{
long sum = 0 ;
int [][] used = new int[H + 2][W + 2];
used[position.get(i).fi][position.get(i).se] = 1 ;
used[position.get(j).fi][position.get(j).se] = 1 ;
Set<IntPair> or = new HashSet<>(P[i].get(k));
or.addAll(P[j].get(l));
for(IntPair v : or) sum += grid[v.fi][v.se];
max = max(max , sum);
}
}
}
}
out.println(max);
}
public static void main(String[] args)
{
new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start();
}
public void run()
{
solve();
out.flush();
}
boolean is_over(int y , int x , int H , int W ) { return y < 0 || y >= H || x < 0 || x >= W ; }
public record IntPair(int fi , int se) { public String toString() { return fi +" "+ se ;} }
public record LongPair(long fi , long se) { public String toString() { return fi +" "+ se ;} }
public record Edge(int to , long weight) { }
public record State(int now , long dist) { }
public double dist(LongPair p1 , LongPair p2) { return Math.sqrt((p1.fi - p2.fi) * (p1.fi - p2.fi) + (p1.se - p2.se) * (p1.se - p2.se)); }
public int max(int ... a) { int max = -1 ; for(int p : a) max = Math.max(max , p); return max; }
public int min(int ... a) { int min = Integer.MAX_VALUE ; for(int p : a) min = Math.min(min , p); return min; }
public long max(long ... a) { long max = -1 ; for(long p : a) max = Math.max(max , p); return max; }
public long min(long ... a) { long min = Long.MAX_VALUE ; for(long p : a) min = Math.min(min , p); return min; }
public int sum(int ... a) { int sum = 0 ; for(int p : a) sum += p ; return sum ;}
public long sum(long ... a) { long sum = 0 ; for(long p : a) sum += p ; return sum ;}
public int abs(int a , int b) { return (int) Math.abs(a - b) ; }
public long abs(long a , long b) { return (long) Math.abs(a - b) ; }
public int pow(int a , int b) { return (int) Math.pow(a , b) ; }
public long pow(long a , long b) { return (long) Math.pow(a , b) ; }
public long rec(long a) { return a == 1 ? 1 : a * rec(a - 1); }
public int [] rev(int [] a) { int [] r = new int[a.length] ; int idx = a.length ; for(int p : a) r[--idx] = p ; return r ; }
public long [] rev(long [] a) { long [] r = new long[a.length] ; int idx = a.length ; for(long p : a) r[--idx] = p ; return r ; }
public int gcd(int a, int b) { return b == 0 ? a: gcd(b, a % b); }
public int lcm(int a, int b) { return a / gcd(a, b) * b; }
public long gcd(long a, long b) { return b == 0 ? a: gcd(b, a % b); }
public long lcm(long a, long b) { return a / gcd(a, b) * b; }
public int gcd(int ... a) { int gcd = 0 ; for(int p : a) gcd = gcd(gcd , p) ; return gcd ; }
public long gcd(long ... a) { long gcd = 0L ; for(long p : a) gcd = gcd(gcd , p) ; return gcd ; }
public int lcm(int ... a) { int lcm = 1 ; for(int p : a) lcm = lcm(lcm , p) ; return lcm ; }
public long lcm(long ... a) { long lcm = 1 ; for(long p : a) lcm = lcm(lcm , p) ; return lcm ; }
public BigInteger lcm(BigInteger... arr) { return Stream.of(arr).reduce((x, y) -> lcm(x, y)).orElse(BigInteger.ONE); }
public BigInteger gcd(BigInteger[] arr) { return Stream.of(arr).reduce(BigInteger::gcd).orElse(BigInteger.ZERO); }
public BigInteger lcm(BigInteger x, BigInteger y) { return x.multiply(y).divide(Objects.nonNull(gcd(x, y)) ? gcd(x, y) : BigInteger.ONE); }
public BigInteger gcd(BigInteger x, BigInteger y) { return (Objects.nonNull(x) ? x : BigInteger.ONE).gcd(y); }
public char upper(char c) { return (char)('A' + (c - 'a')); }
public char lower(char c) { return (char)('a' + (c - 'A')); }
public void yn(boolean a) { out.println(a ? yes : no); }
public String rev(String a) { return new StringBuilder(a).reverse().toString(); }
public void fill(int [] a , int v) { Arrays.fill(a , v); }
public void fill(long [] a , long v) { Arrays.fill(a , v); }
public void fill(int [][] a , int v) { for(int [] aa : a) fill(aa , v) ; }
public void fill(long [][] a , long v) { for(long [] aa : a) fill(aa , v) ; }
public void fill(int [][][] a , int v) { for(int [][] aa : a) fill(aa , v); }
public void fill(long [][][] a , long v) { for(long [][] aa : a) fill(aa , v); }
public int [] copy(int [] a) { return Arrays.copyOf(a , a.length); }
public long [] copy(long [] a) { return Arrays.copyOf(a , a.length); }
public String bin(long a , int len) { String b = Long.toBinaryString(a); while(b.length() < len) b = "0" + b ; return b ; }
public void debug(int [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(long [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(double [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(String [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(char [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(boolean [] a) { char [] c = conv(a); debug(c); fl();}
public void debug(int [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(long [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(double [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(String [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(char [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(boolean [][] a) { char [][] c = new char [a.length][a[0].length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = conv(a[i]) ; debug(c); fl();}
private char [] conv(boolean [] a) { char [] c = new char[a.length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = a[i] ? 'O' : 'X' ; return c ; }
private void fl() { out.flush(); }
public List<Integer> [] Graph(int n) { List<Integer> [] G = new ArrayList[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new ArrayList<>(); return G ; }
public List<Edge> [] GraphW(int n) { List<Edge> [] G = new ArrayList[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new ArrayList<>(); return G ; }
public mint pow(long a, long b , long mod)
{
long res = 1;
while (b > 0)
{
if ((b & 1) != 0)
{
res = (res * a) % mod ;
}
a = (a * a) % mod ;
b >>= 1;
}
return new mint(res , mod);
}
public mint [] rec(int n , long mod) { mint [] r = new mint[n + 1]; r[0] = new mint(1 , mod); for(int i = 1 ; i <= n ; i ++ ) r[i] = r[i - 1].multiply(new mint(i + 1, mod)); return r ; }
public PrintWriter out = new PrintWriter(System.out);
public In in = new In();
public final long MOD7 = 1000000007;
public final long MOD9 = 998244353;
public final int inf = (1 << 30);
public final long lnf = (1L << 60);
public final String yes = "Yes";
public final String no = "No" ;
public final char [] dir = {'U','R','D','L'};
public final int [] dy4 = {-1,0,1,0};
public final int [] dx4 = {0,1,0,-1};
public final int [] dy8 = {-1,-1,-1,0,1,1,1,0};
public final int [] dx8 = {-1,0,1,1,1,0,-1,-1};
}
class mint {
private long value;
private final long MOD;
public mint(long value, long MOD) {
this.MOD = MOD;
this.value = (value % MOD + MOD) % MOD;
}
public mint add(mint other) {
return new mint((this.value + other.value) % MOD, MOD);
}
public mint subtract(mint other) {
return new mint((this.value - other.value + MOD) % MOD, MOD);
}
public mint multiply(mint other) {
return new mint((this.value * other.value) % MOD, MOD);
}
public mint inverse() {
return new mint(pow(this.value, MOD - 2), MOD);
}
public mint divide(mint other) {
return this.multiply(other.inverse());
}
private long pow(long a, long b) {
long res = 1;
while (b > 0) {
if ((b & 1) != 0) {
res = (res * a) % MOD;
}
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
public long getVal() {
return value;
}
@Override
public String toString() {
return String.valueOf(value);
}
}
class Bigmint {
private BigInteger mod;
public Bigmint(long mod)
{
this.mod = convert(mod);
}
public BigInteger add(long a, long b)
{
BigInteger A = convert(a) , B = convert(b);
return A.add(B).mod(mod);
}
public BigInteger subtract(long a, long b)
{
BigInteger A = convert(a) , B = convert(b);
return A.subtract(B).mod(mod);
}
public BigInteger multiply(long a, long b)
{
BigInteger A = convert(a) , B = convert(b);
return A.multiply(B).mod(mod);
}
public BigInteger divide(long a, long b)
{
BigInteger A = convert(a) , B = convert(b);
BigInteger inverseB = B.modInverse(mod);
return A.multiply(inverseB).mod(mod);
}
private BigInteger convert(long a)
{
return new BigInteger(Long.toString(a));
}
}
class SegmentTree
{
private int n ;
private long init ;
private long [] tree ;
private int size ;
private BinaryOperator<Long> op ;
SegmentTree(int size , long init , BinaryOperator<Long> op)
{
this.size = size;
this.init = init ;
this.op = op ;
n = 1 ;
while(n <= size) n *= 2 ;
this.tree = new long[2 * n];
for(int i = 0 ; i < 2 * n ; i ++ ) tree[i] = init ;
}
void update(int index , long value)
{
index += n ;
tree[index] = value ;
while(index > 0)
{
index /= 2 ;
tree[index] = op.apply(tree[2 * index] , tree[2 * index + 1]);
}
}
long query(int l , int r)
{
l += n ; r += n ;
long res = init ;
while(l < r)
{
if(l % 2 == 1){ res = op.apply(res , tree[l]) ; l ++ ; }
l /= 2 ;
if(r % 2 == 1){ res = op.apply(res , tree[r - 1]) ; r -- ; }
r /= 2 ;
}
return res ;
}
void debug()
{
for(int i = n ; i < n + size ; i ++ )
{
System.out.print(tree[i]+" ");
}
System.out.println();
}
}
class LazySegmentTree
{
private long[] Dat;
private long[] Laz;
private int N;
private long E0;
private long E1;
private LongBinaryOperator F;
private LongBinaryOperator G;
private LongBinaryOperator H;
private LongBinaryOperator P;
private int[] Stack = new int[64];
//初期配列 , dat(関与しない値) , lazy(関与しない値) , dat() , dat&lazy() , lazy() , lazy*len()
public LazySegmentTree(int n, long e0, long e1, LongBinaryOperator f, LongBinaryOperator g, LongBinaryOperator h, LongBinaryOperator p)
{
this.E0 = e0;
this.E1 = e1;
this.F = f; this.G = g; this.H = h; this.P = p;
int k = 1;
while (k <= n) k <<= 1;
this.Dat = new long[k << 1];
this.Laz = new long[k << 1];
this.N = k;
Arrays.fill(Dat, E0);
Arrays.fill(Laz, E1);
}
public LazySegmentTree(long[] src, long e0, long e1, LongBinaryOperator f, LongBinaryOperator g, LongBinaryOperator h, LongBinaryOperator p)
{
this(src.length, e0, e1, f, g, h, p);
build(src);
}
private void build(long[] src)
{
System.arraycopy(src, 0, Dat, N, src.length);
for (int i = N - 1; i > 0; i--) Dat[i] = F.applyAsLong(Dat[i << 1 | 0], Dat[i << 1 | 1]);
}
public void update(int l, int r, long v)
{
if (l >= r) return;
int m = updown(l, r);
l += N; r += N;
for (; l < r; l >>= 1, r >>= 1)
{
if ((l & 1) != 0) {Laz[l] = H.applyAsLong(Laz[l], v); l++;}
if ((r & 1) != 0) {r--; Laz[r] = H.applyAsLong(Laz[r], v);}
}
for (int i = 0; i < m; i++)
{
int k = Stack[i];
Dat[k] = F.applyAsLong(calcDat(k << 1 | 0), calcDat(k << 1 | 1));
}
}
public long query(int i)
{
int k = 1;
int l = 0, r = N;
while (k < N)
{
int kl = k << 1 | 0;
int kr = k << 1 | 1;
Dat[k] = F.applyAsLong(calcDat(kl), calcDat(kr));
int m = (l + r) >> 1;
if (m > i) {r = m; k = kl;}
else {l = m; k = kr;}
}
return Dat[k];
}
public long query(int l, int r)
{
if (l >= r) return E0;
updown(l, r);
long resL = E0, resR = E0;
for (l += N, r += N; l < r; l >>= 1, r >>= 1)
{
if ((l & 1) != 0) resL = F.applyAsLong(resL, calcDat(l++));
if ((r & 1) != 0) resR = F.applyAsLong(calcDat(--r), resR);
}
return F.applyAsLong(resL, resR);
}
private int updown(int l, int r)
{
if (l >= r) return 0;
int i = 0;
int kl = l + N, kr = r + N;
for (int x = kl / (kl & -kl) >> 1, y = kr / (kr & -kr) >> 1; 0 < kl && kl < kr; kl >>= 1, kr >>= 1)
{
if (kl <= x) Stack[i++] = kl;
if (kr <= y) Stack[i++] = kr;
}
for (; kl > 0; kl >>= 1) Stack[i++] = kl;
int m = i;
while (i > 0) calcDat(Stack[--i]);
return m;
}
private long calcDat(int k)
{
long lz = Laz[k];
if (lz != E1)
{
int w = N / Integer.highestOneBit(k);
Dat[k] = G.applyAsLong(Dat[k], P.applyAsLong(lz, w));
if (k < N)
{
int l = k << 1 | 0, r = k << 1 | 1;
Laz[l] = H.applyAsLong(Laz[l], lz);
Laz[r] = H.applyAsLong(Laz[r], lz);
}
Laz[k] = E1;
}
return Dat[k];
}
void debug()
{
for(int i = Dat.length - N ; i < Dat.length - 1; i ++ )
{
System.out.print(Dat[i]+" ");
}
System.out.println();
}
}
class In
{
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}else{
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte()) return buffer[ptr++]; else return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private boolean hasNext() {
while(hasNextByte() && !isPrintableChar(buffer[ptr])) {
ptr++;
}
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while(isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while(true){
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
}else if(b == -1 || !isPrintableChar(b)){
return minus ? -n : n;
}else{
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public char nextChar() {
return next().charAt(0);
}
public int [] IntArray(int n) {
final int [] Array = new int [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = nextInt();
}
return Array;
}
public int [][] IntArray(int n , int m) {
final int [][] Array = new int [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = IntArray(m);
}
return Array;
}
public long [] LongArray(int n) {
final long [] Array = new long [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = nextLong();
}
return Array;
}
public long [][] LongArray(int n , int m) {
final long [][] Array = new long [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = LongArray(m);
}
return Array;
}
public String [] StringArray(int n) {
final String [] Array = new String [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next();
}
return Array;
}
public char [] CharArray(int n) {
final char [] Array = new char[n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next().charAt(0);
}
return Array;
}
public char [][] CharArray(int n , int m) {
final char [][] Array = new char [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next().toCharArray();
}
return Array;
}
public char [][] CharArray2(int n , int m) {
final char [][] Array = new char [n][m];
for(int i = 0 ; i < n ; i ++ ) {
for(int j = 0 ; j < m ; j ++ ) {
Array[i][j] = next().charAt(0);
}
}
return Array;
}
}