oj.uz

답안 #1114094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114094 2024-11-18T07:43:43 Z adiyer Bomb (IZhO17_bomb) C++17
28 / 100
 1000 ms 105544 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;
}
 
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)
      |

Subtask #1
28.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3152 KB Output isn't correct
2 Incorrect 2 ms 3408 KB Output isn't correct
3 Incorrect 17 ms 63312 KB Output isn't correct
4 Incorrect 17 ms 63312 KB Output isn't correct
5 Incorrect 2 ms 3152 KB Output isn't correct
6 Incorrect 2 ms 3152 KB Output isn't correct
7 Correct 2 ms 3152 KB Output is correct
8 Correct 4 ms 3408 KB Output is correct
9 Correct 5 ms 3408 KB Output is correct
10 Correct 4 ms 3408 KB Output is correct
11 Correct 4 ms 3408 KB Output is correct
12 Correct 3 ms 3580 KB Output is correct
13 Correct 4 ms 3268 KB Output is correct
14 Correct 3 ms 3408 KB Output is correct
15 Correct 4 ms 3576 KB Output is correct
16 Correct 4 ms 3408 KB Output is correct
17 Correct 8 ms 3656 KB Output is correct
18 Correct 6 ms 3664 KB Output is correct
19 Correct 9 ms 5712 KB Output is correct
20 Correct 9 ms 5712 KB Output is correct
21 Correct 7 ms 3408 KB Output is correct
22 Correct 8 ms 3664 KB Output is correct
23 Correct 14 ms 5712 KB Output is correct
24 Correct 10 ms 5712 KB Output is correct
25 Incorrect 13 ms 5712 KB Output isn't correct
26 Correct 10 ms 5900 KB Output is correct
27 Correct 14 ms 11344 KB Output is correct
28 Correct 20 ms 11600 KB Output is correct
29 Correct 97 ms 11856 KB Output is correct
30 Incorrect 69 ms 14824 KB Output isn't correct
31 Incorrect 58 ms 12112 KB Output isn't correct
32 Incorrect 66 ms 14416 KB Output isn't correct
33 Correct 156 ms 15164 KB Output is correct
34 Correct 20 ms 11600 KB Output is correct
35 Incorrect 39 ms 15096 KB Output isn't correct
36 Incorrect 21 ms 15184 KB Output isn't correct
37 Correct 4 ms 3408 KB Output is correct
38 Execution timed out 1063 ms 102220 KB Time limit exceeded
39 Correct 5 ms 3408 KB Output is correct
40 Incorrect 347 ms 34128 KB Output isn't correct
41 Correct 5 ms 3408 KB Output is correct
42 Correct 16 ms 5712 KB Output is correct
43 Execution timed out 1038 ms 103588 KB Time limit exceeded
44 Incorrect 37 ms 15176 KB Output isn't correct
45 Execution timed out 1050 ms 102196 KB Time limit exceeded
46 Execution timed out 1062 ms 104520 KB Time limit exceeded
47 Execution timed out 1033 ms 102984 KB Time limit exceeded
48 Execution timed out 1038 ms 101192 KB Time limit exceeded
49 Execution timed out 1041 ms 99400 KB Time limit exceeded
50 Execution timed out 1063 ms 104232 KB Time limit exceeded
51 Execution timed out 1044 ms 104048 KB Time limit exceeded
52 Execution timed out 1027 ms 102372 KB Time limit exceeded
53 Execution timed out 1033 ms 101196 KB Time limit exceeded
54 Execution timed out 1020 ms 102216 KB Time limit exceeded
55 Execution timed out 1049 ms 104560 KB Time limit exceeded
56 Execution timed out 1016 ms 102184 KB Time limit exceeded
57 Execution timed out 1073 ms 99400 KB Time limit exceeded
58 Execution timed out 1027 ms 102476 KB Time limit exceeded
59 Execution timed out 1032 ms 104084 KB Time limit exceeded
60 Execution timed out 1041 ms 104776 KB Time limit exceeded
61 Execution timed out 1069 ms 99404 KB Time limit exceeded
62 Execution timed out 1012 ms 102852 KB Time limit exceeded
63 Execution timed out 1070 ms 105032 KB Time limit exceeded
64 Execution timed out 1065 ms 105544 KB Time limit exceeded
65 Execution timed out 1054 ms 104244 KB Time limit exceeded
66 Execution timed out 1053 ms 104264 KB Time limit exceeded
67 Execution timed out 1064 ms 103792 KB Time limit exceeded
68 Execution timed out 1046 ms 102196 KB Time limit exceeded
69 Execution timed out 1059 ms 104776 KB Time limit exceeded
70 Execution timed out 1059 ms 84808 KB Time limit exceeded
71 Execution timed out 1058 ms 99400 KB Time limit exceeded
72 Execution timed out 1065 ms 104320 KB Time limit exceeded
73 Execution timed out 1070 ms 99324 KB Time limit exceeded
74 Execution timed out 1036 ms 103496 KB Time limit exceeded
75 Execution timed out 1053 ms 102216 KB Time limit exceeded
76 Execution timed out 1071 ms 99440 KB Time limit exceeded
77 Execution timed out 1035 ms 102216 KB Time limit exceeded
78 Execution timed out 1043 ms 102288 KB Time limit exceeded
79 Execution timed out 1053 ms 103740 KB Time limit exceeded
80 Execution timed out 1049 ms 103080 KB Time limit exceeded
81 Execution timed out 1041 ms 104012 KB Time limit exceeded
82 Execution timed out 1078 ms 99400 KB Time limit exceeded
83 Execution timed out 1047 ms 102216 KB Time limit exceeded
84 Execution timed out 1036 ms 104520 KB Time limit exceeded
85 Execution timed out 1044 ms 105544 KB Time limit exceeded
86 Execution timed out 1064 ms 104520 KB Time limit exceeded
87 Execution timed out 1058 ms 104008 KB Time limit exceeded
88 Execution timed out 1055 ms 103088 KB Time limit exceeded
89 Execution timed out 1034 ms 102472 KB Time limit exceeded
90 Execution timed out 1070 ms 84552 KB Time limit exceeded
91 Execution timed out 1039 ms 105032 KB Time limit exceeded
92 Execution timed out 1061 ms 102216 KB Time limit exceeded
93 Execution timed out 1038 ms 102984 KB Time limit exceeded
94 Execution timed out 1051 ms 104520 KB Time limit exceeded
95 Execution timed out 1069 ms 104436 KB Time limit exceeded
96 Execution timed out 1045 ms 103716 KB Time limit exceeded
97 Execution timed out 1050 ms 103224 KB Time limit exceeded
98 Execution timed out 1054 ms 103044 KB Time limit exceeded
99 Execution timed out 1022 ms 102216 KB Time limit exceeded
100 Execution timed out 1055 ms 104008 KB Time limit exceeded