fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/rope>
  3. #define clr(x) memset((x), 0, sizeof(x))
  4. #define all(x) (x).begin(), (x).end()
  5. #define pb push_back
  6. #define mp make_pair
  7. #define For(i, st, en) for(int i=(st); i<=(int)(en); i++)
  8. #define Ford(i, st, en) for(int i=(st); i>=(int)(en); i--)
  9. #define forn(i, n) for(int i=0; i<(int)(n); i++)
  10. #define ford(i, n) for(int i=(n)-1; i>=0; i--)
  11. #define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
  12. #define in(x) int (x); input((x));
  13. #define x first
  14. #define y second
  15. #define less(a,b) ((a) < (b) - EPS)
  16. #define more(a,b) ((a) > (b) + EPS)
  17. #define eq(a,b) (fabs((a) - (b)) < EPS)
  18. #define remax(a, b) ((a) = (b) > (a) ? (b) : (a))
  19. #define remin(a, b) ((a) = (b) < (a) ? (b) : (a))
  20.  
  21. using namespace std;
  22.  
  23. using namespace __gnu_cxx;
  24.  
  25. template <typename T>
  26. T gcd(T a, T b) {
  27.     while (b > 0) {
  28.         a %= b;
  29.         swap(a, b);
  30.     }
  31.     return a;
  32. }
  33. typedef long double ld; template <class _T> inline _T sqr(const _T& x) {return x * x;} template <class _T> inline string tostr(const _T& a) {ostringstream os(""); os << a; return os.str();} const ld PI = 3.1415926535897932384626433832795L; const double EPS = 1e-9; char TEMPORARY_CHAR; typedef long long ll; typedef unsigned long long ull; typedef set < int > SI; typedef vector < int > VI; typedef vector < vector < int > > VVI; typedef map < string, int > MSI; typedef pair < int, int > PII; const int INF = 1e9; inline void input(int &a) {a = 0; while (((TEMPORARY_CHAR = getchar()) > '9' || TEMPORARY_CHAR < '0') && (TEMPORARY_CHAR != '-')){} char neg = 0; if (TEMPORARY_CHAR == '-') {neg = 1; TEMPORARY_CHAR = getchar();} while (TEMPORARY_CHAR <= '9' && TEMPORARY_CHAR >= '0') {a = 10 * a + TEMPORARY_CHAR - '0'; TEMPORARY_CHAR = getchar();} if (neg) a = -a;} inline void out(long long a) {if (!a) putchar('0'); if (a < 0) {putchar('-'); a = -a;} char s[20]; int i; for(i = 0; a; ++i) {s[i] = '0' + a % 10; a /= 10;} ford(j, i) putchar(s[j]);} inline int nxt() {in(ret); return ret;}
  34.  
  35. //inline void input(long long &a) {a = 0; while (((TEMPORARY_CHAR = getchar()) > '9' || TEMPORARY_CHAR < '0') && (TEMPORARY_CHAR != '-')){} char neg = 0; if (TEMPORARY_CHAR == '-') {neg = 1; TEMPORARY_CHAR = getchar();} while (TEMPORARY_CHAR <= '9' && TEMPORARY_CHAR >= '0') {a = 10 * a + TEMPORARY_CHAR - '0'; TEMPORARY_CHAR = getchar();} if (neg) a = -a;}
  36.  
  37. vector <vector <int> > dr[25];
  38.  
  39. vector <int> cur;
  40.  
  41. void rec(int s, int prev, vector <vector <int> > & z) {
  42.     if (s == 0) {
  43.         z.push_back(cur);
  44.         return;
  45.     }
  46.     for (int i = 1; i <= min(prev, s); ++i) {
  47.         cur.push_back(i);
  48.         rec(s - i, i, z);
  49.         cur.pop_back();
  50.     }
  51. }
  52.  
  53. int main()
  54. {
  55.     in(n);
  56.     dr[0].push_back(vector <int>());
  57.     for (int i = 1; i <= n; ++i) {
  58.         rec(i, i, dr[i]);
  59.     }
  60.     for (int i = 1; i <= n; ++i) {
  61.         for (int j = 0; j < (int)dr[i].size(); ++j) {
  62.             sort(all(dr[i][j]));
  63.         }
  64.         sort(all(dr[i]));
  65.     }
  66.  
  67.  
  68.     int c[n];
  69.  
  70.     for (int i = 0; i < n; ++i) {
  71.         c[i] = nxt();
  72.     }
  73.  
  74.     sort(c, c + n);
  75.  
  76.     if (c[n - 1] != n) {
  77.         puts("NO");
  78.         return 0;
  79.     }
  80.  
  81.     char dp[n + 1][dr[n].size()];
  82.     clr(dp);
  83.     dp[0][0] = 1;
  84.     int s = 0;
  85.  
  86.     for (int i = 0; i < n; ++i) {
  87.         s += 1;
  88.         for (int j = 0; j < dr[s].size(); ++j) {
  89.         	int pos = lower_bound(all(dr[s][j]), c[i]) - dr[s][j].begin();
  90.             if (pos != dr[s][j].size() && dr[s][j][pos] == c[i]) {
  91.             	vector <int> d = dr[s][j];
  92.                 d.erase(d.begin() + pos);
  93.  
  94.                 for (int k = 0; k < dr[c[i] - 1].size(); ++k) {
  95.                     if (dr[c[i] - 1][k].size() == 1) continue;
  96.                     vector <int> q;
  97.                     merge(all(d), all(dr[c[i] - 1][k]), back_inserter(q));
  98.                     int p = lower_bound(all(dr[s - 1]), q) - dr[s - 1].begin();
  99.                     if (dp[i][p]) {
  100.                         dp[i + 1][j] = 1;
  101.                         break;
  102.                     }
  103.                 }
  104.             }
  105.         }
  106.     }
  107.  
  108.     for (int i = 0; i < dr[n].size(); ++i) {
  109.         if (dp[n][i]) {
  110.             puts("YES");
  111.             return 0;
  112.         }
  113.     }
  114.     puts("NO");
  115.     return 0;
  116. }
Success #stdin #stdout 0s 3444KB
comments (?)
stdin
copy 
5
1 1 5 2 1
stdout
copy 
NO
https://ideone.com/676rE7
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!