답안 #758629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758629 2023-06-15T02:02:35 Z NK_ 호화 벙커 (IZhO13_burrow) C++17
100 / 100
441 ms 8352 KB
#include <bits/stdc++.h>

using namespace std;

/////////////////////// MACROS ////////////////////////////////////////////
using ll = long long;
using ld = long double;
using db = double;
using str = string;

using pi = pair<int,int>;
using pl = pair<ll,ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<str>;
using vc = vector<char>;
using vpi = vector<pi>;
using vpl = vector<pl>;

#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcTU> using PR = pair<T,U>;
tcTU> using umap = unordered_map<T, U>;
tcT> using uset = unordered_set<T>;
tcT> using mset = multiset<T>;

#define mp make_pair
#define f first
#define s second

#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define ppb pop_back()
#define ppf pop_front()
#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

// LOOPS
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_, a)
#define each(a,x) for (auto& a: x)

/////////////////////// IMPORANT VARS /////////////////////////////////////

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INFL = ll(3e18)+10;
const int INF = int(1e9)+10;
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;
tcT> using pql = priority_queue<T,vector<T>,less<T>>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define nl '\n'

constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { 
	return x == 0 ? 0 : 31-__builtin_clz(x); }
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }
 
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
 
tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }
 
tcTU> T fstTrue(T lo, T hi, U f) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	} 
	return lo;
}
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
	sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { // don't erase
	auto it = t.find(u); assert(it != end(t));
	t.erase(it); } // element that doesn't exist from (multi)set


// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;

// tcT> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
// #define ook order_of_key
// #define fbo find_by_order

// struct chash { 
// 	const uint64_t C = ll(2e18*PI)+71;
// 	const int RANDOM = rng();
// 	ll operator()(ll x) const {
// 		return __builtin_bswap64((x^RANDOM)*C); }
// };
// template<class K,class V> using um = unordered_map<K,V,chash>;
// template<class K,class V> using ht = gp_hash_table<K,V,chash>;
// template<class K,class V> V get(ht<K,V>& u, K x) {
// 	auto it = u.find(x); return it == end(u) ? 0 : it->s; }

/////////////////////// OUPUT /////////////////////////////////////////////
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) {
	#ifdef LOCAL
		return b ? "true" : "false";
	#else
		return ts((int)b);
	#endif
}
tcTU> str ts(pair<T,U> p) {
	#ifdef LOCAL
		return "("+ts(p.f)+", "+ts(p.s)+")";
	#else
		return ts(p.f)+" "+ts(p.s);
	#endif
}

tcTU> str ts(V<pair<T, U>> v) {
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;
	#endif
}

tcT> str ts(T v) {
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;

	#endif
}

///////////////////////// DEBUG ///////////////////////////////////////////
#define tcTUU tcT, class ...U
void DBG() { cerr << "]" << "\e[0m" << endl; }
tcTUU> void DBG(const T& t, const U&... u) {
	cerr << ts(t); if (sizeof...(u)) cerr << ", ";
	DBG(u...); }
#ifdef LOCAL
	#define dbg(...) cerr << "\e[1m" << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
	#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
		 << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
	#define dbg(...) 0
	#define chk(...) 0
#endif	

///////////////////////// FILE I/O ////////////////////////////////////////
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setPrec() { cout << fixed << setprecision(15); }
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void setIO(str s = "") {
	unsyncIO(); setPrec();
	#ifndef LOCAL	
		if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for USACO
	#endif
}

///////////////////////// TEMPLATE ABOVE //////////////////////////////////

// REMEMBER
// - Don't Focus On Only One Approach
// - Read And Understand Problem Fully
// - Think Of Edges Cases
// - Implement Carefully
// - Always Check For Overflows
// - Reset Global Variables
// - Look At The Bigger Picture
// - Don't Get Discouraged, You Can Pull It Back

int get(vi h) {
   	vi stk = {-1};
   	int ans = 0;
   	h.pb(-1);
   	dbg(h);
   	F0R(i, sz(h)) {
   		dbg(i, stk);
   		while(stk.bk != -1 && h[stk.bk] > h[i]) {
   			int lst = stk.bk; stk.ppb;
   			int area = (i - stk.bk - 1) * h[lst];
   			dbg(stk.bk, i, h[lst], area);
   			ckmax(ans, area);
   		}
   		stk.pb(i);
   	}
   	dbg(ans);
   	return ans;
}

void solve() {
	int N, M, K; cin >> N >> M >> K;

	V<vi> A(N, vi(M)); each(x, A) each(v, x) cin >> v;

	auto check = [&](int x) {

		V<vi> R(N, vi(M, 0));

		R0F(i, N) {
			F0R(j, M) {
				if (A[i][j] >= x) {
					R[i][j] = 1;
					if (i+1 < N) R[i][j] += R[i+1][j];
				}
			}
		}

		int ans = 0;
		F0R(i, N) ckmax(ans, get(R[i]));

		return ans;
	};

	int lo = 0, hi = INF;
	while(lo < hi) {
		int mid = (lo + hi + 1) / 2;
		if (check(mid) >= K) lo = mid;
		else hi = mid - 1;
	}
	cout << lo << " " << check(lo) << nl;


}

int main() {
	setIO(); 

	int TT = 1;
	// cin >> TT;

	rep(TT) solve();
	
	exit(0-0);
}

Compilation message

burrow.cpp: In function 'int get(vi)':
burrow.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
burrow.cpp:226:5: note: in expansion of macro 'dbg'
  226 |     dbg(h);
      |     ^~~
burrow.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
burrow.cpp:228:6: note: in expansion of macro 'dbg'
  228 |      dbg(i, stk);
      |      ^~~
burrow.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
burrow.cpp:232:7: note: in expansion of macro 'dbg'
  232 |       dbg(stk.bk, i, h[lst], area);
      |       ^~~
burrow.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
burrow.cpp:237:5: note: in expansion of macro 'dbg'
  237 |     dbg(ans);
      |     ^~~
burrow.cpp: In function 'void setIn(str)':
burrow.cpp:201:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
burrow.cpp: In function 'void setOut(str)':
burrow.cpp:202:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 228 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 340 KB Output is correct
9 Correct 10 ms 500 KB Output is correct
10 Correct 19 ms 596 KB Output is correct
11 Correct 32 ms 812 KB Output is correct
12 Correct 21 ms 756 KB Output is correct
13 Correct 28 ms 724 KB Output is correct
14 Correct 57 ms 1608 KB Output is correct
15 Correct 61 ms 1612 KB Output is correct
16 Correct 65 ms 1604 KB Output is correct
17 Correct 69 ms 2328 KB Output is correct
18 Correct 168 ms 3184 KB Output is correct
19 Correct 187 ms 4204 KB Output is correct
20 Correct 344 ms 5396 KB Output is correct
21 Correct 320 ms 6712 KB Output is correct
22 Correct 441 ms 8352 KB Output is correct
23 Correct 431 ms 8268 KB Output is correct
24 Correct 285 ms 6216 KB Output is correct
25 Correct 290 ms 8224 KB Output is correct