답안 #1114096

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114096 2024-11-18T07:45:35 Z adiyer Bomb (IZhO17_bomb) C++17
30 / 100
1000 ms 123384 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[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;
}
 
ll ff(ll W){
	ll l = 0, r = m + 1;
	while(r - l > 1){
		if(f(W, md)) l = md;
		else r = md;
	}
	return l * W;
}

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];
	ll l = 0, r = n + 1;
	while(r - l > 2){
		ll m1 = l + (r - l) / 3;
		ll m2 = r - (r - l) / 3; 
		if(ff(m1) < ff(m2)) l = m1;
		else r = m2;
	}
	ll ans = 0;
	for(ll i = max(1ll, l - 20); i <= min(n, r + 20); i++) ans = max(ans, ff(i));
	cout << ans;
}
 
 
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)
      |
# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 26960 KB Output isn't correct
2 Incorrect 29 ms 29196 KB Output isn't correct
3 Incorrect 73 ms 72784 KB Output isn't correct
4 Incorrect 64 ms 67964 KB Output isn't correct
5 Incorrect 13 ms 26960 KB Output isn't correct
6 Incorrect 10 ms 26960 KB Output isn't correct
7 Correct 22 ms 27096 KB Output is correct
8 Correct 96 ms 29008 KB Output is correct
9 Correct 92 ms 29008 KB Output is correct
10 Correct 54 ms 26960 KB Output is correct
11 Correct 98 ms 29008 KB Output is correct
12 Correct 73 ms 27132 KB Output is correct
13 Correct 48 ms 26960 KB Output is correct
14 Correct 68 ms 26960 KB Output is correct
15 Correct 73 ms 26960 KB Output is correct
16 Correct 118 ms 29008 KB Output is correct
17 Correct 125 ms 29264 KB Output is correct
18 Correct 142 ms 29264 KB Output is correct
19 Correct 175 ms 29520 KB Output is correct
20 Correct 177 ms 29520 KB Output is correct
21 Correct 138 ms 29368 KB Output is correct
22 Correct 146 ms 29264 KB Output is correct
23 Correct 162 ms 29520 KB Output is correct
24 Correct 172 ms 29264 KB Output is correct
25 Incorrect 224 ms 29520 KB Output isn't correct
26 Correct 163 ms 29520 KB Output is correct
27 Correct 224 ms 36432 KB Output is correct
28 Correct 210 ms 36432 KB Output is correct
29 Correct 470 ms 39196 KB Output is correct
30 Incorrect 456 ms 39768 KB Output isn't correct
31 Incorrect 439 ms 38992 KB Output isn't correct
32 Incorrect 570 ms 39248 KB Output isn't correct
33 Correct 676 ms 41984 KB Output is correct
34 Correct 316 ms 38792 KB Output is correct
35 Incorrect 445 ms 41808 KB Output isn't correct
36 Correct 576 ms 41988 KB Output is correct
37 Correct 63 ms 29208 KB Output is correct
38 Incorrect 782 ms 123008 KB Output isn't correct
39 Correct 66 ms 29008 KB Output is correct
40 Execution timed out 1077 ms 57680 KB Time limit exceeded
41 Correct 75 ms 29008 KB Output is correct
42 Correct 286 ms 29600 KB Output is correct
43 Incorrect 783 ms 123172 KB Output isn't correct
44 Correct 707 ms 41808 KB Output is correct
45 Incorrect 632 ms 123168 KB Output isn't correct
46 Execution timed out 1057 ms 122952 KB Time limit exceeded
47 Incorrect 637 ms 122952 KB Output isn't correct
48 Incorrect 595 ms 123156 KB Output isn't correct
49 Incorrect 738 ms 122952 KB Output isn't correct
50 Incorrect 624 ms 123064 KB Output isn't correct
51 Incorrect 503 ms 122952 KB Output isn't correct
52 Execution timed out 1074 ms 122952 KB Time limit exceeded
53 Incorrect 604 ms 122952 KB Output isn't correct
54 Incorrect 631 ms 122952 KB Output isn't correct
55 Incorrect 778 ms 123156 KB Output isn't correct
56 Incorrect 548 ms 123168 KB Output isn't correct
57 Execution timed out 1072 ms 122952 KB Time limit exceeded
58 Execution timed out 1075 ms 123152 KB Time limit exceeded
59 Execution timed out 1069 ms 123208 KB Time limit exceeded
60 Incorrect 678 ms 123160 KB Output isn't correct
61 Incorrect 603 ms 122952 KB Output isn't correct
62 Incorrect 876 ms 122956 KB Output isn't correct
63 Incorrect 761 ms 123160 KB Output isn't correct
64 Incorrect 674 ms 123384 KB Output isn't correct
65 Incorrect 664 ms 123156 KB Output isn't correct
66 Incorrect 760 ms 123168 KB Output isn't correct
67 Incorrect 562 ms 122952 KB Output isn't correct
68 Incorrect 605 ms 122952 KB Output isn't correct
69 Execution timed out 1068 ms 123152 KB Time limit exceeded
70 Execution timed out 1072 ms 105032 KB Time limit exceeded
71 Execution timed out 1068 ms 122952 KB Time limit exceeded
72 Execution timed out 1070 ms 123128 KB Time limit exceeded
73 Execution timed out 1072 ms 122952 KB Time limit exceeded
74 Execution timed out 1074 ms 122952 KB Time limit exceeded
75 Execution timed out 1062 ms 122952 KB Time limit exceeded
76 Execution timed out 1059 ms 122952 KB Time limit exceeded
77 Execution timed out 1085 ms 123112 KB Time limit exceeded
78 Execution timed out 1077 ms 123136 KB Time limit exceeded
79 Execution timed out 1079 ms 123124 KB Time limit exceeded
80 Execution timed out 1051 ms 123160 KB Time limit exceeded
81 Execution timed out 1075 ms 122952 KB Time limit exceeded
82 Execution timed out 1068 ms 122952 KB Time limit exceeded
83 Execution timed out 1062 ms 122896 KB Time limit exceeded
84 Execution timed out 1069 ms 123060 KB Time limit exceeded
85 Execution timed out 1077 ms 122952 KB Time limit exceeded
86 Execution timed out 1053 ms 122952 KB Time limit exceeded
87 Execution timed out 1066 ms 122952 KB Time limit exceeded
88 Execution timed out 1079 ms 122952 KB Time limit exceeded
89 Execution timed out 1073 ms 122952 KB Time limit exceeded
90 Execution timed out 1069 ms 105032 KB Time limit exceeded
91 Execution timed out 1055 ms 122952 KB Time limit exceeded
92 Execution timed out 1070 ms 122952 KB Time limit exceeded
93 Execution timed out 1062 ms 122952 KB Time limit exceeded
94 Execution timed out 1072 ms 122952 KB Time limit exceeded
95 Execution timed out 1062 ms 123124 KB Time limit exceeded
96 Execution timed out 1061 ms 122952 KB Time limit exceeded
97 Execution timed out 1075 ms 122952 KB Time limit exceeded
98 Execution timed out 1058 ms 123172 KB Time limit exceeded
99 Execution timed out 1067 ms 123120 KB Time limit exceeded
100 Execution timed out 1065 ms 122956 KB Time limit exceeded