結果
| 問題 | No.3596 Queen Score Attack 1 |
| コンテスト | |
| ユーザー |
 nosu kuro
|
| 提出日時 | 2026-07-24 21:18:17 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,061 bytes |
| 記録 | |
| コンパイル時間 | 3,468 ms |
| コンパイル使用メモリ | 358,728 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-07-24 21:18:33 |
| 合計ジャッジ時間 | 7,338 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | TLE * 1 -- * 30 |
ソースコード
#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN
#include __FILE__
#include <atcoder/convolution>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint1000000007;
int main(void){
int t; cin >> t;
for(;t--;){
int h, w; cin >> h >> w;
vector<vector<ll>> a(h,vector<ll>(w));
int i,j;
rep(i,h) rep(j,w) cin >> a[i][j];
bool ans = false;
rep(i,h){
rep(j,w){
vector<vector<ll>> v(h,vector<ll>(w,-1e17));
queue<pair<int,int>> q;
q.push({i,j});
v[i][j] = a[i][j];
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
int k;
rep(k,h){
if(k==x) continue;
if(v[k][y] + v[x][y] + a[k][y]> 0){
ans = true;
break;
}else if(v[k][y] < v[x][y] + a[k][y]){
v[k][y] = v[x][y]+a[k][y];
q.push({k,y});
}
}
rep(k,w){
if(k==y) continue;
if(v[x][k] + v[x][y] + a[x][k]> 0){
ans = true;
break;
}else if(v[x][k] < v[x][y] + a[x][k]){
v[x][k] = v[x][y]+a[x][k];
q.push({x,k});
}
}
int nx = x+1, ny = y+1;
while(0<=nx && 0<=ny && nx<h && ny<w){
if(v[nx][ny] + v[x][y] + a[nx][ny]> 0){
ans = true;
break;
}else if(v[nx][ny] < v[x][y] + a[nx][ny]){
v[nx][ny] = v[x][y] + a[nx][ny];
q.push({nx,ny});
}
nx++;ny++;
}
nx = x+1; ny = y-1;
while(0<=nx && 0<=ny && nx<h && ny<w){
if(v[nx][ny] + v[x][y] + a[nx][ny]> 0){
ans = true;
break;
}else if(v[nx][ny] < v[x][y] + a[nx][ny]){
v[nx][ny] = v[x][y] + a[nx][ny];
q.push({nx,ny});
}
nx++;ny--;
}
nx = x-1; ny = y-1;
while(0<=nx && 0<=ny && nx<h && ny<w){
if(v[nx][ny] + v[x][y] + a[nx][ny]> 0){
ans = true;
break;
}else if(v[nx][ny] < v[x][y] + a[nx][ny]){
v[nx][ny] = v[x][y] + a[nx][ny];
q.push({nx,ny});
}
nx--;ny--;
}
nx = x-1; ny = y+1;
while(0<=nx && 0<=ny && nx<h && ny<w){
if(v[nx][ny] + v[x][y] + a[nx][ny]> 0){
ans = true;
break;
}else if(v[nx][ny] < v[x][y] + a[nx][ny]){
v[nx][ny] = v[x][y] + a[nx][ny];
q.push({nx,ny});
}
nx--;ny++;
}
if(ans) break;
}
if(ans) break;
}
if(ans) break;
}
if(ans){
cout << "infinite\n";
}else{
cout << "finite\n";
}
}
}
#else
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(i=0;i<(n);i++)
#define all(a) a.begin(), a.end()
namespace nskr{
//nyaan氏の実装をかなり参考にした
template <int id = 0>
struct modint{
int v;
static int& MOD(){
static int mod = 998244353;
return mod;
}
static int get_mod() { return MOD(); }
static void set_mod(int m) { MOD() = m; }
modint() :v(0){}
modint(long long x) : v( (x>=0 ? x%MOD() : (x%MOD() + MOD()))){}
long long val() const {return v;}
modint& operator+=(const modint& x){if((v+=x.v) >= MOD()) v-=MOD(); return *this; }
modint& operator-=(const modint& x){if((v-=x.v) < 0 ) v+=MOD(); return *this; }
modint& operator*=(const modint& x){v = (int)(1ll * v * x.v % MOD()); return *this;}
modint& operator/=(const modint& x){v = (int)(1ll * v * x.inv().val() % MOD()); return *this;}
modint operator-() const {return modint(-v);}
modint operator+() const {return *this;}
modint operator+(const modint& x) const {return modint(*this)+=x;}
modint operator-(const modint& x) const {return modint(*this)-=x;}
modint operator*(const modint& x) const {return modint(*this)*=x;}
modint operator/(const modint& x) const {return modint(*this)/=x;}
bool operator== (const modint& x) const {return v==x.v;}
bool operator!= (const modint& x) const {return v!=x.v;}
friend ostream &operator<<(ostream &os, const modint &p) { return os << p.v; }
friend istream &operator>>(istream &is, modint &a) {
int t;
is >> t;
a = modint<id>(t);
return (is);
}
modint pow(unsigned long long n) const {
modint ret(1), mul(v);
while(n){
if(n&1) ret *= mul;
mul *= mul;
n >>=1;
}
return ret;
}
modint inv() const{ //参考： https://qiita.com/sesame0224/items/f2ac77c367f588c0d29d
int a = v, b = MOD(), u = 1, w = 0;
while(b){
int t = a/b;
swap(a -= t*b, b);
swap(u -= t*w, w);
}
u%=MOD();
return(u<0?u+MOD():u);
}
};
template<typename mint>
struct combination{
vector<mint> fac;
combination():fac({mint(1)}){}
void preculc(int n){
fac.reserve(n);
while(fac.size() <= n){
fac.push_back( (*fac.rbegin()) * mint(fac.size()) );
}
return;
}
mint comb(int n, int r){
if(r>n || r<0 || n<0) return 0;
if(n-r < r) r = n-r;
if(fac.size() > n) return fac[n] * fac[r].inv() * fac[n-r].inv();
else{
mint ret = fac[r].inv();
for(;r--;) ret *= (n-r+1);
return ret;
}
}
};
}
#endif