답안 #759253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
759253 2023-06-16T00:49:31 Z NK_ UFO (IZhO14_ufo) C++17
35 / 100
2000 ms 17192 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

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

	V<vl> A(N, vl(M));
	F0R(i, N) F0R(j, M) {
		cin >> A[i][j];
	}

	F0R(l_, K) {
		char dir; cin >> dir;
		dbg(l_, dir);
		if (dir == 'N') {
			int c, h; cin >> c >> h; --c;

			int t = 0;
			F0R(r, N) if (A[r][c] >= h) {
				A[r][c]--;
				if (++t == T) break;
			}
		}

		if (dir == 'S') {
			int c, h; cin >> c >> h; --c;
			
			int t = 0;
			R0F(r, N) if (A[r][c] >= h) {
				A[r][c]--;
				if (++t == T) break;
			}
		}

		if (dir == 'W') {
			int r, h; cin >> r >> h; --r;
			
			int t = 0;
			F0R(c, M) if (A[r][c] >= h) {
				A[r][c]--;
				if (++t == T) break;
			}
		}	

		if (dir == 'E') {
			int r, h; cin >> r >> h; --r;

			int t = 0;
			R0F(c, M) if (A[r][c] >= h) {
				A[r][c]--;
				if (++t == T) break;
			}
		}
	}	

	V<vl> P(N+1, vl(M+1));
	FOR(i, 1, N+1) FOR(j, 1, M+1) {
		P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + A[i-1][j-1];
	}

	auto qry = [&](int r1, int c1, int r2, int c2) {
		return P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1];
	};

	ll ans = 0;
	FOR(r, 1, N+1) FOR(c, 1, M+1) if (r+X-1 <= N && c+X-1 <= M) {
		ckmax(ans, qry(r, c, r+X-1, c+X-1));
	}

	cout << ans << nl;	
}

int main() {
	setIO(); 

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

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

Compilation message

ufo.cpp: In function 'void solve()':
ufo.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
ufo.cpp:232:3: note: in expansion of macro 'dbg'
  232 |   dbg(l_, dir);
      |   ^~~
ufo.cpp: In function 'void setIn(str)':
ufo.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); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
ufo.cpp: In function 'void setOut(str)':
ufo.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 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 13 ms 1140 KB Output is correct
6 Correct 53 ms 8008 KB Output is correct
7 Execution timed out 2076 ms 8916 KB Time limit exceeded
8 Execution timed out 2087 ms 8916 KB Time limit exceeded
9 Execution timed out 2081 ms 8532 KB Time limit exceeded
10 Execution timed out 2084 ms 8916 KB Time limit exceeded
11 Execution timed out 2085 ms 8788 KB Time limit exceeded
12 Execution timed out 2078 ms 8916 KB Time limit exceeded
13 Execution timed out 2089 ms 12032 KB Time limit exceeded
14 Correct 943 ms 17192 KB Output is correct
15 Execution timed out 2077 ms 8916 KB Time limit exceeded
16 Execution timed out 2084 ms 8788 KB Time limit exceeded
17 Execution timed out 2079 ms 11988 KB Time limit exceeded
18 Execution timed out 2080 ms 10580 KB Time limit exceeded
19 Execution timed out 2031 ms 9684 KB Time limit exceeded
20 Execution timed out 2084 ms 15956 KB Time limit exceeded