oj.uz

답안 #1114047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114047 2024-11-18T07:01:20 Z adiyer Bomb (IZhO17_bomb) C++17
49 / 100
 442 ms 99484 KB 
// 194.67
#pragma optimize ("g",on)
#pragma GCC optimize("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
 
#include <bits/stdc++.h>

#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0);
#define bitcount(n) __builtin_popcountll(n)
#define puts(x) cout << (x ? "YES\n" : "NO\n");
#define ent (i == n ? '\n' : ' ')
#define all(x) x.begin(), x.end()
#define md ((l + r) >> 1)
#define rv(v) ((v << 1) | 1)
#define lv(v) (v << 1)
#define rs(v) rv(v), md + 1, r
#define ls(v) lv(v), l, md
#define len(s) (int) s.size()
 
#define yes { cout << "YES\n"; return; }
#define no { cout << "NO\n"; return; }
#define skip continue
#define pb push_back
#define S second
#define F first
#define ne !=

// #define int long long
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector < ll > vll;
typedef pair < ll, ll > pll;
typedef vector < pair < ll, ll > > vpll;

const int dx[8] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int N = 2.5e3 + 5;
const int K = 1e5 + 3;
const int MAX = 1e6;
const int mod = 998244353;
const long long inf = 2e9;
const ll o = 1;
 
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

ll n, m, w, h;
ll a[N][N], pref[N][N];

int st[460][460];

char c;

ll get(ll l1, ll r1, ll l2, ll r2){
	return pref[l2][r2] - pref[l1 - 1][r2] - pref[l2][r1 - 1] + pref[l1 - 1][r1 - 1];
}

bool f(ll W, ll H){
	memset(st, 0, sizeof(st));
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= m; j++){
			if(get(i, j, i + H - 1, j + W - 1) >= H * W){
				st[i][j]++;
				st[i + H][j]--;
				st[i][j + W]--;
				st[i + H][j + W]++;
			}
			st[i][j] += st[i - 1][j] + st[i][j - 1] - st[i - 1][j - 1];
			if(a[i][j] && !st[i][j]) return 0;
		}
	}
	return 1;
}

void output(){
	cin >> n >> m, w = m, h = n;
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= m; j++)
			cin >> c, a[i][j] = c - '0';
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= m; j++) 
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + a[i][j];
	if(n <= 450 && m <= 450){
		ll ans = 0;
		for(ll x = 1; x <= m; x++){
			ll l = 0, r = n + 1;
			while(r - l > 1){
				if(f(x, md)) l = md;
				else r = md;
			}
			ans = max(ans, x * l);
		}
		cout << ans;
		return;
	}
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= m; j++){
			if(!a[i][j - 1] && a[i][j]){
				ll l = j, r = m + 1;
				while(r - l > 1){
					if(get(i, j, i, md) == md - j + 1) l = md;
					else r = md;
				}
				w = min(w, l - j + 1);
				// cout << i << ' ' << j << ' ' << l << '\n';
			}
			if(!a[i - 1][j] && a[i][j]){
				ll l = i, r = n + 1;
				while(r - l > 1){
					if(get(i, j, md, j) == md - i + 1) l = md;
					else r = md;
				}
				h = min(h, l - i + 1);
				// cout << i << ' ' << j << ' ' << l << '\n';
			}
		}
	}
	cout << h * w;
}


const bool cases = 0;

signed main(){
//  file("disrupt");
    adiyer();
    int tt = 1;
    if(cases) cin >> tt;
    for(int i = 1; i <= tt; i++){
//      cout << "Case " << i << ":\n";
        output();
        // slow();
        // stress();
    }
}

Compilation message

bomb.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize ("g",on)
      |

Subtask #1
49.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 2 ms 3576 KB Output is correct
3 Correct 14 ms 36800 KB Output is correct
4 Correct 13 ms 33616 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 2 ms 3152 KB Output is correct
8 Correct 3 ms 3420 KB Output is correct
9 Correct 3 ms 3408 KB Output is correct
10 Correct 2 ms 3408 KB Output is correct
11 Correct 3 ms 3408 KB Output is correct
12 Correct 3 ms 3408 KB Output is correct
13 Correct 2 ms 3408 KB Output is correct
14 Correct 3 ms 3408 KB Output is correct
15 Correct 3 ms 3576 KB Output is correct
16 Correct 3 ms 3408 KB Output is correct
17 Correct 9 ms 3656 KB Output is correct
18 Correct 7 ms 3664 KB Output is correct
19 Correct 10 ms 5712 KB Output is correct
20 Correct 11 ms 5712 KB Output is correct
21 Correct 9 ms 3408 KB Output is correct
22 Correct 11 ms 3880 KB Output is correct
23 Correct 15 ms 5712 KB Output is correct
24 Correct 9 ms 5712 KB Output is correct
25 Correct 15 ms 5712 KB Output is correct
26 Correct 13 ms 5712 KB Output is correct
27 Correct 39 ms 11088 KB Output is correct
28 Correct 48 ms 11344 KB Output is correct
29 Correct 190 ms 11856 KB Output is correct
30 Correct 228 ms 14928 KB Output is correct
31 Correct 149 ms 12112 KB Output is correct
32 Correct 118 ms 14416 KB Output is correct
33 Correct 442 ms 13408 KB Output is correct
34 Correct 37 ms 11600 KB Output is correct
35 Correct 136 ms 14928 KB Output is correct
36 Incorrect 186 ms 14928 KB Output isn't correct
37 Correct 3 ms 3408 KB Output is correct
38 Correct 118 ms 98564 KB Output is correct
39 Correct 4 ms 3604 KB Output is correct
40 Incorrect 20 ms 25168 KB Output isn't correct
41 Correct 4 ms 3408 KB Output is correct
42 Correct 18 ms 5712 KB Output is correct
43 Correct 124 ms 99484 KB Output is correct
44 Incorrect 356 ms 15184 KB Output isn't correct
45 Incorrect 113 ms 98552 KB Output isn't correct
46 Correct 137 ms 98376 KB Output is correct
47 Incorrect 119 ms 98384 KB Output isn't correct
48 Incorrect 130 ms 98504 KB Output isn't correct
49 Correct 117 ms 98604 KB Output is correct
50 Incorrect 122 ms 98376 KB Output isn't correct
51 Incorrect 117 ms 98376 KB Output isn't correct
52 Incorrect 119 ms 98380 KB Output isn't correct
53 Incorrect 123 ms 98380 KB Output isn't correct
54 Incorrect 123 ms 98376 KB Output isn't correct
55 Incorrect 114 ms 98380 KB Output isn't correct
56 Correct 133 ms 98376 KB Output is correct
57 Incorrect 118 ms 98376 KB Output isn't correct
58 Incorrect 139 ms 98556 KB Output isn't correct
59 Incorrect 115 ms 98540 KB Output isn't correct
60 Correct 119 ms 98376 KB Output is correct
61 Correct 115 ms 98376 KB Output is correct
62 Correct 117 ms 98372 KB Output is correct
63 Correct 116 ms 98468 KB Output is correct
64 Correct 116 ms 98376 KB Output is correct
65 Incorrect 118 ms 98552 KB Output isn't correct
66 Incorrect 122 ms 98376 KB Output isn't correct
67 Incorrect 118 ms 98524 KB Output isn't correct
68 Incorrect 118 ms 98376 KB Output isn't correct
69 Incorrect 119 ms 98376 KB Output isn't correct
70 Incorrect 85 ms 79436 KB Output isn't correct
71 Incorrect 116 ms 98472 KB Output isn't correct
72 Incorrect 117 ms 98376 KB Output isn't correct
73 Incorrect 122 ms 98540 KB Output isn't correct
74 Incorrect 124 ms 98532 KB Output isn't correct
75 Incorrect 114 ms 98376 KB Output isn't correct
76 Incorrect 117 ms 98376 KB Output isn't correct
77 Incorrect 110 ms 98520 KB Output isn't correct
78 Incorrect 117 ms 98376 KB Output isn't correct
79 Incorrect 115 ms 98380 KB Output isn't correct
80 Incorrect 118 ms 98528 KB Output isn't correct
81 Incorrect 126 ms 98376 KB Output isn't correct
82 Incorrect 126 ms 98376 KB Output isn't correct
83 Incorrect 119 ms 98524 KB Output isn't correct
84 Incorrect 112 ms 98532 KB Output isn't correct
85 Incorrect 119 ms 98380 KB Output isn't correct
86 Incorrect 114 ms 98544 KB Output isn't correct
87 Incorrect 116 ms 98388 KB Output isn't correct
88 Incorrect 116 ms 98376 KB Output isn't correct
89 Incorrect 117 ms 98460 KB Output isn't correct
90 Incorrect 89 ms 79336 KB Output isn't correct
91 Incorrect 109 ms 98376 KB Output isn't correct
92 Incorrect 113 ms 98396 KB Output isn't correct
93 Incorrect 127 ms 98632 KB Output isn't correct
94 Incorrect 119 ms 98376 KB Output isn't correct
95 Incorrect 115 ms 98380 KB Output isn't correct
96 Incorrect 117 ms 98376 KB Output isn't correct
97 Incorrect 113 ms 98484 KB Output isn't correct
98 Incorrect 120 ms 98656 KB Output isn't correct
99 Incorrect 117 ms 98456 KB Output isn't correct
100 Incorrect 119 ms 98548 KB Output isn't correct