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

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