oj.uz

답안 #1114044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114044 2024-11-18T06:58:21 Z adiyer Bomb (IZhO17_bomb) C++17
48 / 100
 1000 ms 104724 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){
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= m; j++)
			st[i][j] = 0;
	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]++;
			}
		}
	}
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= m; j++){
			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
48.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 2 ms 4688 KB Output is correct
3 Correct 14 ms 36944 KB Output is correct
4 Correct 14 ms 36868 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 2384 KB Output is correct
8 Correct 1 ms 4688 KB Output is correct
9 Correct 2 ms 4856 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 2 ms 4688 KB Output is correct
12 Correct 2 ms 4432 KB Output is correct
13 Correct 2 ms 4432 KB Output is correct
14 Correct 2 ms 4432 KB Output is correct
15 Correct 2 ms 4688 KB Output is correct
16 Correct 2 ms 4688 KB Output is correct
17 Correct 5 ms 6736 KB Output is correct
18 Correct 4 ms 7160 KB Output is correct
19 Correct 6 ms 9024 KB Output is correct
20 Correct 6 ms 9040 KB Output is correct
21 Correct 4 ms 6736 KB Output is correct
22 Correct 8 ms 6992 KB Output is correct
23 Correct 11 ms 7248 KB Output is correct
24 Correct 5 ms 6992 KB Output is correct
25 Correct 11 ms 7324 KB Output is correct
26 Correct 11 ms 7248 KB Output is correct
27 Correct 230 ms 12104 KB Output is correct
28 Correct 406 ms 14796 KB Output is correct
29 Correct 502 ms 15944 KB Output is correct
30 Correct 966 ms 21908 KB Output is correct
31 Correct 617 ms 19016 KB Output is correct
32 Correct 569 ms 19608 KB Output is correct
33 Execution timed out 1035 ms 27800 KB Time limit exceeded
34 Correct 187 ms 25168 KB Output is correct
35 Correct 936 ms 25420 KB Output is correct
36 Execution timed out 1076 ms 23568 KB Time limit exceeded
37 Correct 1 ms 4688 KB Output is correct
38 Correct 129 ms 101888 KB Output is correct
39 Correct 2 ms 4688 KB Output is correct
40 Incorrect 30 ms 27528 KB Output isn't correct
41 Correct 2 ms 4688 KB Output is correct
42 Correct 13 ms 9040 KB Output is correct
43 Correct 140 ms 101000 KB Output is correct
44 Execution timed out 1060 ms 27804 KB Time limit exceeded
45 Incorrect 117 ms 101704 KB Output isn't correct
46 Correct 142 ms 99144 KB Output is correct
47 Incorrect 135 ms 101708 KB Output isn't correct
48 Incorrect 136 ms 98376 KB Output isn't correct
49 Correct 126 ms 98528 KB Output is correct
50 Incorrect 125 ms 102808 KB Output isn't correct
51 Incorrect 134 ms 104008 KB Output isn't correct
52 Incorrect 132 ms 101704 KB Output isn't correct
53 Incorrect 139 ms 98380 KB Output isn't correct
54 Incorrect 125 ms 101684 KB Output isn't correct
55 Incorrect 149 ms 104012 KB Output isn't correct
56 Correct 150 ms 98376 KB Output is correct
57 Incorrect 129 ms 98376 KB Output isn't correct
58 Incorrect 129 ms 101824 KB Output isn't correct
59 Incorrect 130 ms 103752 KB Output isn't correct
60 Correct 131 ms 103752 KB Output is correct
61 Correct 120 ms 98376 KB Output is correct
62 Correct 121 ms 98376 KB Output is correct
63 Correct 112 ms 104008 KB Output is correct
64 Correct 115 ms 104724 KB Output is correct
65 Incorrect 112 ms 101216 KB Output isn't correct
66 Incorrect 119 ms 104600 KB Output isn't correct
67 Incorrect 113 ms 101008 KB Output isn't correct
68 Incorrect 117 ms 101704 KB Output isn't correct
69 Incorrect 114 ms 98532 KB Output isn't correct
70 Incorrect 83 ms 84376 KB Output isn't correct
71 Incorrect 107 ms 98376 KB Output isn't correct
72 Incorrect 118 ms 104008 KB Output isn't correct
73 Incorrect 108 ms 98384 KB Output isn't correct
74 Incorrect 142 ms 98500 KB Output isn't correct
75 Incorrect 120 ms 98376 KB Output isn't correct
76 Incorrect 123 ms 98524 KB Output isn't correct
77 Incorrect 119 ms 98376 KB Output isn't correct
78 Incorrect 139 ms 100780 KB Output isn't correct
79 Incorrect 115 ms 101704 KB Output isn't correct
80 Incorrect 118 ms 100168 KB Output isn't correct
81 Incorrect 144 ms 101704 KB Output isn't correct
82 Incorrect 118 ms 98516 KB Output isn't correct
83 Incorrect 128 ms 101704 KB Output isn't correct
84 Incorrect 125 ms 104232 KB Output isn't correct
85 Incorrect 126 ms 103996 KB Output isn't correct
86 Incorrect 129 ms 104008 KB Output isn't correct
87 Incorrect 119 ms 104008 KB Output isn't correct
88 Incorrect 121 ms 103240 KB Output isn't correct
89 Incorrect 121 ms 101720 KB Output isn't correct
90 Incorrect 100 ms 80456 KB Output isn't correct
91 Incorrect 124 ms 104008 KB Output isn't correct
92 Incorrect 128 ms 101708 KB Output isn't correct
93 Incorrect 131 ms 103240 KB Output isn't correct
94 Incorrect 129 ms 104100 KB Output isn't correct
95 Incorrect 126 ms 104008 KB Output isn't correct
96 Incorrect 127 ms 101704 KB Output isn't correct
97 Incorrect 129 ms 104008 KB Output isn't correct
98 Incorrect 127 ms 99912 KB Output isn't correct
99 Incorrect 132 ms 101704 KB Output isn't correct
100 Incorrect 131 ms 104156 KB Output isn't correct