oj.uz

답안 #1114045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114045 2024-11-18T06:59:35 Z adiyer Bomb (IZhO17_bomb) C++17
40 / 100
 1000 ms 102996 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], st[N][N];

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
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 51536 KB Output is correct
2 Correct 29 ms 51724 KB Output is correct
3 Correct 18 ms 38480 KB Output is correct
4 Correct 13 ms 30288 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 42 ms 51528 KB Output is correct
8 Correct 121 ms 51484 KB Output is correct
9 Correct 135 ms 51496 KB Output is correct
10 Correct 83 ms 51560 KB Output is correct
11 Correct 133 ms 51536 KB Output is correct
12 Correct 102 ms 51692 KB Output is correct
13 Correct 77 ms 51528 KB Output is correct
14 Correct 116 ms 51528 KB Output is correct
15 Correct 114 ms 51536 KB Output is correct
16 Correct 128 ms 51536 KB Output is correct
17 Correct 543 ms 54000 KB Output is correct
18 Correct 512 ms 53840 KB Output is correct
19 Correct 720 ms 54120 KB Output is correct
20 Correct 683 ms 54096 KB Output is correct
21 Correct 654 ms 53832 KB Output is correct
22 Correct 798 ms 54056 KB Output is correct
23 Correct 928 ms 54096 KB Output is correct
24 Correct 598 ms 54052 KB Output is correct
25 Correct 999 ms 54184 KB Output is correct
26 Correct 868 ms 54180 KB Output is correct
27 Execution timed out 1062 ms 59464 KB Time limit exceeded
28 Execution timed out 1064 ms 59720 KB Time limit exceeded
29 Execution timed out 1070 ms 62288 KB Time limit exceeded
30 Execution timed out 1062 ms 63040 KB Time limit exceeded
31 Execution timed out 1076 ms 60236 KB Time limit exceeded
32 Execution timed out 1079 ms 62536 KB Time limit exceeded
33 Execution timed out 1067 ms 65352 KB Time limit exceeded
34 Execution timed out 1060 ms 59976 KB Time limit exceeded
35 Execution timed out 1048 ms 65116 KB Time limit exceeded
36 Execution timed out 1063 ms 65096 KB Time limit exceeded
37 Correct 145 ms 51536 KB Output is correct
38 Correct 119 ms 98552 KB Output is correct
39 Correct 139 ms 51704 KB Output is correct
40 Incorrect 22 ms 28496 KB Output isn't correct
41 Correct 128 ms 51528 KB Output is correct
42 Correct 779 ms 54176 KB Output is correct
43 Correct 124 ms 100680 KB Output is correct
44 Execution timed out 1068 ms 56392 KB Time limit exceeded
45 Incorrect 114 ms 98376 KB Output isn't correct
46 Correct 136 ms 100936 KB Output is correct
47 Incorrect 121 ms 98472 KB Output isn't correct
48 Incorrect 127 ms 101860 KB Output isn't correct
49 Correct 141 ms 98588 KB Output is correct
50 Incorrect 148 ms 98376 KB Output isn't correct
51 Incorrect 127 ms 98544 KB Output isn't correct
52 Incorrect 132 ms 98600 KB Output isn't correct
53 Incorrect 145 ms 101704 KB Output isn't correct
54 Incorrect 156 ms 101372 KB Output isn't correct
55 Incorrect 129 ms 101448 KB Output isn't correct
56 Correct 166 ms 101920 KB Output is correct
57 Incorrect 124 ms 98480 KB Output isn't correct
58 Incorrect 131 ms 98376 KB Output isn't correct
59 Incorrect 124 ms 98376 KB Output isn't correct
60 Correct 137 ms 101192 KB Output is correct
61 Correct 134 ms 98376 KB Output is correct
62 Correct 127 ms 101704 KB Output is correct
63 Correct 130 ms 98432 KB Output is correct
64 Correct 127 ms 98788 KB Output is correct
65 Incorrect 130 ms 100164 KB Output isn't correct
66 Incorrect 133 ms 98376 KB Output isn't correct
67 Incorrect 138 ms 99144 KB Output isn't correct
68 Incorrect 125 ms 98376 KB Output isn't correct
69 Incorrect 152 ms 101784 KB Output isn't correct
70 Incorrect 92 ms 80416 KB Output isn't correct
71 Incorrect 124 ms 98544 KB Output isn't correct
72 Incorrect 130 ms 102984 KB Output isn't correct
73 Incorrect 129 ms 98548 KB Output isn't correct
74 Incorrect 127 ms 102168 KB Output isn't correct
75 Incorrect 124 ms 101704 KB Output isn't correct
76 Incorrect 134 ms 98536 KB Output isn't correct
77 Incorrect 128 ms 101704 KB Output isn't correct
78 Incorrect 123 ms 100424 KB Output isn't correct
79 Incorrect 126 ms 100128 KB Output isn't correct
80 Incorrect 137 ms 101448 KB Output isn't correct
81 Incorrect 123 ms 98368 KB Output isn't correct
82 Incorrect 124 ms 98376 KB Output isn't correct
83 Incorrect 122 ms 98424 KB Output isn't correct
84 Incorrect 127 ms 102996 KB Output isn't correct
85 Incorrect 132 ms 98380 KB Output isn't correct
86 Incorrect 130 ms 98376 KB Output isn't correct
87 Incorrect 128 ms 98376 KB Output isn't correct
88 Incorrect 135 ms 98376 KB Output isn't correct
89 Incorrect 120 ms 98580 KB Output isn't correct
90 Incorrect 94 ms 82760 KB Output isn't correct
91 Incorrect 110 ms 98372 KB Output isn't correct
92 Incorrect 109 ms 98532 KB Output isn't correct
93 Incorrect 114 ms 101108 KB Output isn't correct
94 Incorrect 120 ms 98572 KB Output isn't correct
95 Incorrect 116 ms 98520 KB Output isn't correct
96 Incorrect 116 ms 98372 KB Output isn't correct
97 Incorrect 113 ms 99996 KB Output isn't correct
98 Incorrect 117 ms 101192 KB Output isn't correct
99 Incorrect 110 ms 98376 KB Output isn't correct
100 Incorrect 120 ms 98376 KB Output isn't correct