Submission #33700


Source Code Expand

Copy
//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

Submission Time
Task C - 積み重ね
User wotsushi
Language C++ (GCC 4.4.7)
Score 100
Code Size 2836 Byte
Status AC
Exec Time 23 ms
Memory 896 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 44
Set Name Test Cases
All 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 02_maxrnd_00.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_increase_00.txt, 03_increase_01.txt, 03_increase_02.txt, 04_decrease_00.txt, 04_decrease_01.txt, 04_decrease_02.txt, 05_same_00.txt, 05_same_01.txt
Case Name Status Exec Time Memory
00_min.txt AC 21 ms 760 KB
00_sample_01.txt AC 21 ms 820 KB
00_sample_02.txt AC 21 ms 756 KB
00_sample_03.txt AC 21 ms 792 KB
00_sample_04.txt AC 22 ms 796 KB
00_sample_05.txt AC 19 ms 784 KB
01_rnd_00.txt AC 21 ms 764 KB
01_rnd_01.txt AC 22 ms 796 KB
01_rnd_02.txt AC 21 ms 764 KB
01_rnd_03.txt AC 21 ms 784 KB
01_rnd_04.txt AC 21 ms 796 KB
01_rnd_05.txt AC 21 ms 796 KB
01_rnd_06.txt AC 20 ms 796 KB
01_rnd_07.txt AC 20 ms 788 KB
01_rnd_08.txt AC 20 ms 792 KB
01_rnd_09.txt AC 21 ms 788 KB
02_maxrnd_00.txt AC 21 ms 788 KB
02_maxrnd_01.txt AC 21 ms 788 KB
02_maxrnd_02.txt AC 21 ms 792 KB
02_maxrnd_03.txt AC 23 ms 816 KB
02_maxrnd_04.txt AC 21 ms 784 KB
02_maxrnd_05.txt AC 21 ms 752 KB
02_maxrnd_06.txt AC 21 ms 788 KB
02_maxrnd_07.txt AC 21 ms 764 KB
02_maxrnd_08.txt AC 21 ms 792 KB
02_maxrnd_09.txt AC 21 ms 788 KB
02_maxrnd_10.txt AC 20 ms 728 KB
02_maxrnd_11.txt AC 19 ms 796 KB
02_maxrnd_12.txt AC 19 ms 816 KB
02_maxrnd_13.txt AC 21 ms 780 KB
02_maxrnd_14.txt AC 21 ms 896 KB
02_maxrnd_15.txt AC 21 ms 792 KB
02_maxrnd_16.txt AC 20 ms 792 KB
02_maxrnd_17.txt AC 21 ms 756 KB
02_maxrnd_18.txt AC 21 ms 788 KB
02_maxrnd_19.txt AC 21 ms 788 KB
03_increase_00.txt AC 21 ms 792 KB
03_increase_01.txt AC 21 ms 788 KB
03_increase_02.txt AC 21 ms 792 KB
04_decrease_00.txt AC 21 ms 792 KB
04_decrease_01.txt AC 21 ms 788 KB
04_decrease_02.txt AC 21 ms 764 KB
05_same_00.txt AC 21 ms 792 KB
05_same_01.txt AC 21 ms 784 KB