oj.uz

답안 #1114099

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

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)
      |

Subtask #1
36.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 26960 KB Output is correct
2 Correct 27 ms 29008 KB Output is correct
3 Correct 94 ms 69448 KB Output is correct
4 Correct 93 ms 67940 KB Output is correct
5 Correct 16 ms 26960 KB Output is correct
6 Correct 11 ms 27128 KB Output is correct
7 Correct 25 ms 26960 KB Output is correct
8 Correct 78 ms 29008 KB Output is correct
9 Correct 100 ms 29008 KB Output is correct
10 Correct 52 ms 26960 KB Output is correct
11 Correct 110 ms 29008 KB Output is correct
12 Correct 77 ms 27068 KB Output is correct
13 Correct 75 ms 26960 KB Output is correct
14 Correct 87 ms 26960 KB Output is correct
15 Correct 100 ms 27020 KB Output is correct
16 Correct 112 ms 29176 KB Output is correct
17 Correct 214 ms 29264 KB Output is correct
18 Correct 175 ms 29440 KB Output is correct
19 Correct 295 ms 29520 KB Output is correct
20 Correct 280 ms 29440 KB Output is correct
21 Correct 194 ms 29264 KB Output is correct
22 Correct 206 ms 29264 KB Output is correct
23 Correct 263 ms 29604 KB Output is correct
24 Correct 267 ms 29264 KB Output is correct
25 Incorrect 361 ms 29520 KB Output isn't correct
26 Correct 292 ms 29520 KB Output is correct
27 Correct 249 ms 36432 KB Output is correct
28 Correct 365 ms 35152 KB Output is correct
29 Correct 641 ms 39200 KB Output is correct
30 Incorrect 561 ms 39760 KB Output isn't correct
31 Incorrect 544 ms 38992 KB Output isn't correct
32 Incorrect 543 ms 39248 KB Output isn't correct
33 Incorrect 613 ms 41988 KB Output isn't correct
34 Correct 292 ms 38736 KB Output is correct
35 Correct 414 ms 42188 KB Output is correct
36 Correct 638 ms 42064 KB Output is correct
37 Correct 85 ms 29008 KB Output is correct
38 Execution timed out 1051 ms 123128 KB Time limit exceeded
39 Correct 96 ms 29008 KB Output is correct
40 Execution timed out 1051 ms 58108 KB Time limit exceeded
41 Correct 85 ms 29008 KB Output is correct
42 Correct 302 ms 29520 KB Output is correct
43 Incorrect 798 ms 125728 KB Output isn't correct
44 Correct 759 ms 42200 KB Output is correct
45 Incorrect 742 ms 122952 KB Output isn't correct
46 Execution timed out 1052 ms 123464 KB Time limit exceeded
47 Incorrect 652 ms 122952 KB Output isn't correct
48 Incorrect 514 ms 126020 KB Output isn't correct
49 Incorrect 634 ms 122952 KB Output isn't correct
50 Incorrect 567 ms 123292 KB Output isn't correct
51 Execution timed out 1006 ms 123720 KB Time limit exceeded
52 Incorrect 619 ms 123160 KB Output isn't correct
53 Incorrect 598 ms 124232 KB Output isn't correct
54 Execution timed out 1042 ms 125464 KB Time limit exceeded
55 Incorrect 950 ms 123380 KB Output isn't correct
56 Incorrect 627 ms 124956 KB Output isn't correct
57 Execution timed out 1072 ms 122952 KB Time limit exceeded
58 Execution timed out 1054 ms 124644 KB Time limit exceeded
59 Execution timed out 1055 ms 122952 KB Time limit exceeded
60 Incorrect 633 ms 123416 KB Output isn't correct
61 Incorrect 597 ms 122952 KB Output isn't correct
62 Incorrect 837 ms 125212 KB Output isn't correct
63 Incorrect 933 ms 123640 KB Output isn't correct
64 Incorrect 594 ms 126416 KB Output isn't correct
65 Incorrect 521 ms 123400 KB Output isn't correct
66 Incorrect 576 ms 123400 KB Output isn't correct
67 Incorrect 586 ms 122952 KB Output isn't correct
68 Incorrect 527 ms 123132 KB Output isn't correct
69 Execution timed out 1040 ms 123208 KB Time limit exceeded
70 Execution timed out 1065 ms 105164 KB Time limit exceeded
71 Execution timed out 1052 ms 122952 KB Time limit exceeded
72 Execution timed out 1020 ms 123696 KB Time limit exceeded
73 Execution timed out 1073 ms 122952 KB Time limit exceeded
74 Execution timed out 1030 ms 123468 KB Time limit exceeded
75 Execution timed out 1051 ms 124504 KB Time limit exceeded
76 Execution timed out 1080 ms 123144 KB Time limit exceeded
77 Execution timed out 1045 ms 124488 KB Time limit exceeded
78 Execution timed out 1069 ms 122952 KB Time limit exceeded
79 Execution timed out 1070 ms 122952 KB Time limit exceeded
80 Execution timed out 1053 ms 122952 KB Time limit exceeded
81 Execution timed out 1067 ms 123380 KB Time limit exceeded
82 Execution timed out 1044 ms 122952 KB Time limit exceeded
83 Execution timed out 1041 ms 124744 KB Time limit exceeded
84 Execution timed out 1069 ms 122952 KB Time limit exceeded
85 Execution timed out 1073 ms 123128 KB Time limit exceeded
86 Execution timed out 1059 ms 122952 KB Time limit exceeded
87 Execution timed out 1035 ms 123464 KB Time limit exceeded
88 Execution timed out 1048 ms 125256 KB Time limit exceeded
89 Execution timed out 1036 ms 124944 KB Time limit exceeded
90 Execution timed out 1064 ms 105252 KB Time limit exceeded
91 Execution timed out 1068 ms 122952 KB Time limit exceeded
92 Execution timed out 1063 ms 122952 KB Time limit exceeded
93 Execution timed out 1058 ms 123816 KB Time limit exceeded
94 Execution timed out 1071 ms 122956 KB Time limit exceeded
95 Execution timed out 1068 ms 123100 KB Time limit exceeded
96 Execution timed out 1046 ms 123720 KB Time limit exceeded
97 Execution timed out 1070 ms 122952 KB Time limit exceeded
98 Execution timed out 1042 ms 125796 KB Time limit exceeded
99 Execution timed out 1031 ms 125256 KB Time limit exceeded
100 Execution timed out 1040 ms 123468 KB Time limit exceeded