Submission #169013
Source Code Expand
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstring> #include <fstream> #include <iostream> #include <map> #include <queue> #include <unordered_map> #include <utility> #include <set> #include <sstream> #include <stack> #include <string> #include <sys/time.h> #include <vector> using namespace std; #define i64 int64_t #define rep(i, n) for(i64 i = 0; i < ((i64)(n)); ++i) #define sz(v) ((i64)((v).size())) #define bit(n) (((i64)1)<<((i64)(n))) #define all(v) (v).begin(), (v).end() template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){} template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); } template <class ...Ts> std::ostream& operator<<(std::ostream &os, const std::tuple<Ts...> &t){ os << "("; deploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; } template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; } template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; } template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.front() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; } template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.top() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; } template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> &p){ os << "(" << p.first << ", " << p.second << ")"; return os; } template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; } template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; } #define DEBUG0() { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << std::endl; } #define DEBUG1(var0) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << std::endl; } #define DEBUG2(var0, var1) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << std::endl; } #define DEBUG3(var0, var1, var2) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << std::endl; } #define DEBUG4(var0, var1, var2, var3) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << std::endl; } #define DEBUG5(var0, var1, var2, var3, var4) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << std::endl; } #define DEBUG6(var0, var1, var2, var3, var4, var5) { char buf[100]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << ", " << (#var5) << "=" << (var5) << std::endl; } #define ASSERT(f) { if(!(f)){ DEBUG0(); while(true); }} const i64 MAX = 33; i64 xs[MAX]; i64 ys[MAX]; map<tuple<i64, i64, i64, i64, i64>, i64> dp; i64 recur(i64 x0, i64 y0, i64 x1, i64 y1, i64 mask) { rep(i, MAX)if(mask & bit(i)) ASSERT(x0 <= xs[i] && xs[i] <= x1 && y0 <= ys[i] && ys[i] <= y1); auto index = make_tuple(x0, y0, x1, y1, mask); if(dp.count(index)) return dp[index]; i64 res = 0; rep(i, MAX){ if(~mask & bit(i)) continue; i64 next_masks[4] = {0, 0, 0, 0}; rep(j, MAX)if((mask & bit(j)) && i != j){ i64 t = 0; if(xs[i] < xs[j]) t |= 1; if(ys[i] < ys[j]) t |= 2; next_masks[t] |= bit(j); } i64 score = (x1 - x0 + 1) + (y1 - y0 + 1) - 1; score += recur(x0, y0, xs[i] - 1, ys[i] - 1, next_masks[0]); score += recur(xs[i] + 1, y0, x1, ys[i] - 1, next_masks[1]); score += recur(x0, ys[i] + 1, xs[i] - 1, y1, next_masks[2]); score += recur(xs[i] + 1, ys[i] + 1, x1, y1, next_masks[3]); res = max(res, score); } return dp[index] = res; } int main() { i64 w, h, n; cin >> w >> h >> n; rep(i, n) cin >> ys[i] >> xs[i]; cout << recur(1, 1, h, w, bit(n) - 1) << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 金塊ゲーム |
User | Komaki |
Language | C++ (G++ 4.6.4) |
Score | 0 |
Code Size | 5290 Byte |
Status | CE |
Compile Error
In file included from /usr/include/c++/4.6/unordered_map:35:0, from ./Main.cpp:10: /usr/include/c++/4.6/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the upcoming ISO C++ standard, C++0x. This support is currently experimental, and must be enabled with the -std=c++0x or -std=gnu++0x compiler options. ./Main.cpp:26:48: warning: variadic templates only available with -std=c++0x or -std=gnu++0x [enabled by default] ./Main.cpp: In function ‘void deploy(std::ostream&, const TUPLE&)’: ./Main.cpp:26:134: error: ‘get’ was not declared in this scope ./Main.cpp: At global scope: ./Main.cpp:27:17: warning: variadic templates only available with -std=c++0x or -std=gnu++0x [enabled by default] ./Main.cpp:27:73: error: ‘tuple’ in namespace ‘std’ does not name a type ./Main.cpp:27:78: error: ISO C++ forbids declaration of ‘parameter’ with no type [-fpermissive] ./Main.cpp:27:83: error: expected ‘,’ or ‘...’ before ‘<’ token ./Mai...