Submission #33700

---

Source Code Expand

//template ver2.00
//------------------------------------------

//include
//------------------------------------------
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>

using namespace std;

//conversion
//------------------------------------------
inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
template<class T> inline T is_inner(T x, T a, T b) {return a <= x && x < b;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define MP make_pair
#define EACH(i, c) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(c, e) ((c).find(e) != (c).end())

//repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a);i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

//IO
//------------------------------------------
#define LF(x) cout << (x) << endl;
#define LFA(a, n) cout << a[0]; FOR(itr, 1, n) {cout << " " << a[itr];} cout << endl;
#define LFP(x, w) cout << setprecision((w)); cout << setiosflags(ios::fixed); cout << (x) << endl;

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INF = 1e9;
const int DI[] = {0, 1, 0, -1};
const int DJ[] = {1, 0, -1, 0};

//clear memory
//--------------------------------------------
#define CLR(a) memset((a), 0 , sizeof(a))

//debug
//--------------------------------------------
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DUMPA(a, n) cerr << #a << " = {" << a[0]; FOR(itr, 1, n) { cout << ", " << a[itr]; } cerr << "}" << endl;
#define DUMPAA(a, n, m) REP(itr, n) {REP(jtr, m) {cout << a[itr][jtr] << " ";} cout << endl;}

const int N = 50;

int n;
int w[N];

int dp[N + 1];


void init()
{
}

void solve()
{
     fill(dp, dp + N + 1, INF);
     REP(i, n) {
	  int x = INF;
	  int k = -1;
	  REP(j, n) {
	       if (w[i] <= dp[j] && dp[j] <= x) {
		    x = dp[j];
		    k = j;
	       }
	  }
	  dp[k] = w[i];
     }
     int ans = 0;
     REP(i, n) if(dp[i] < INF) ++ans;
     LF(ans);
}


int main()
{
     init();
     cin >> n;
     REP(i, n) cin >> w[i];
     solve();
     return 0;
}

Submission Info

Judge Result