0
Your rating: None

CodeChef submission 67737 (C++ 4.0.0-8)

CodeChef submission 67737 (C++ 4.0.0-8) plaintext list. Status: AC, problem E5, contest . By dejandenib (Dejan), 2009-08-09 19:31:21.
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cctype>
  6. #include <cmath>
  7. #include <iostream>
  8. #include <sstream>
  9. #include <string>
  10. #include <utility>
  11. #include <vector>
  12. #include <cassert>
  13. #include <ctime>
  14. #include <queue>
  15. using namespace std;
  16. #define VAR(a,b) __typeof(b) a=(b)
  17. #define REP(i,n) for(int _n=n, i=0;i<_n;++i)
  18. #define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
  19. #define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
  20. #define FOREACH(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
  21. #define ALL(c) (c).begin(),(c).end()
  22. typedef long long LL;
  23. const int INF = 1000000000; const LL INFLL = LL(INF) * LL(INF);
  24. typedef vector<int> VI; typedef vector<string> VS; typedef vector<VI> VVI;
  25. template<class T> inline int size(const T&c) { return c.size(); }
  26. int rint() { int x; if(scanf("%d",&x)!=1) return -1; return x; }
  27. string rstring() { char buf[1000]; scanf("%s",buf); return buf; }
  28. //}}}
  29.  
  30. const int MAXN = 30;
  31.  
  32. LL cache[MAXN+1][MAXN+1];
  33.  
  34. inline int nextz(int n,int z,int a) {
  35.   if(a==0) return max(z-1,0);
  36.   else if(a<=z) return -1;
  37.   else return a-1;
  38. }
  39.  
  40. LL calc(int n, int z) {
  41.   LL &res = cache[n][z];
  42.   if(res != -1) return res;
  43.   if(n==0) res=1;
  44.   else {
  45.     res = 0;
  46.     REP(i,n) {
  47.       int z2 = nextz(n,z,i);
  48.       if(z2 != -1) res += calc(n-1, z2);
  49.     }
  50.   }
  51.   return res;
  52. }
  53.  
  54. int main() {
  55.   memset(cache, -1, sizeof(cache));
  56.   int ntc = rint();
  57.   REP(tc,ntc) {
  58.     int n = rint();
  59.     assert(n>=1 && n<=MAXN);
  60.     int plen = rint();
  61.     vector<int> p(plen);
  62.     REP(i,plen) p[i] = rint()-1;
  63.     int z = 0;
  64.     LL res = 0;
  65.     bool bad = false;
  66.     REP(i,plen) {
  67.       int a = p[i];
  68.       z = nextz(n,z,a);
  69.       if(z==-1) { bad=true; break; }
  70.       --n;
  71.       FOREACH(it,p) if(*it > a) --*it;
  72.     }
  73.     if(!bad) res = calc(n,z);
  74.     printf("%lld\n", res);
  75.   }
  76. }
  77.

Comments