Submission #33429


Source Code Expand

Copy
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)



const int MAX_LR = 3010;

int L, R;
vector<int> adj[MAX_LR];
bool vis[MAX_LR], usd[MAX_LR];
int lev[MAX_LR + 1], mat[MAX_LR];

bool augment(int l) {
  if (l == L) return true;
  if (vis[l]) return false;
  vis[l] = true;
  rep (i, adj[l].size()) {
    int r = adj[l][i], l2 = mat[r];
    if (lev[l2] > lev[l] && augment(l2)) {
      mat[r] = l;
      return true;
    }
  }
  return false;
}

int bipartite_matching() {
  fill(mat, mat + R, L);
  memset(usd, 0, sizeof(bool) * L);
  bool update;
  do {
    fill(lev, lev + L + 1, -1);
    lev[L] = R;
    queue<int> que;
    rep (l, L) if (!usd[l]) {
      que.push(l);
      lev[l] = 0;
    }
    while (!que.empty()) {
      int l = que.front();
      que.pop();
      rep (i, adj[l].size()) {
        int r = adj[l][i], l2 = mat[r];
        if (lev[l2] < 0) {
          lev[l2] = lev[l] + 1;
          que.push(l2);
        }
      }
    }

    memset(vis, 0, sizeof(bool) * L);
    update = false;
    rep (l, L) if (!usd[l] && augment(l)) usd[l] = update = true;
  } while (update);

  return count(usd, usd + L, true);
}



int main() {
  int N;
  while (1 == scanf("%d", &N)) {
    vector<int> W(N);
    rep (i, N) scanf("%d", &W[i]);

    L = R = N;
    rep (l, L) adj[l].clear();
    rep (l, N) rep (r, N) {
      if (l < r && W[l] >= W[r]) adj[l].pb(r);
    }
    printf("%d\n", N - bipartite_matching());
  }

  return 0;
}

Submission Info

Submission Time
Task C - 積み重ね
User iwiwi
Language C++ (G++ 4.6.4)
Score 100
Code Size 2091 Byte
Status AC
Exec Time 80 ms
Memory 948 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

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 792 KB
00_sample_01.txt AC 21 ms 920 KB
00_sample_02.txt AC 21 ms 792 KB
00_sample_03.txt AC 22 ms 948 KB
00_sample_04.txt AC 21 ms 796 KB
00_sample_05.txt AC 22 ms 792 KB
01_rnd_00.txt AC 21 ms 792 KB
01_rnd_01.txt AC 21 ms 912 KB
01_rnd_02.txt AC 21 ms 784 KB
01_rnd_03.txt AC 21 ms 920 KB
01_rnd_04.txt AC 21 ms 916 KB
01_rnd_05.txt AC 21 ms 920 KB
01_rnd_06.txt AC 21 ms 916 KB
01_rnd_07.txt AC 21 ms 916 KB
01_rnd_08.txt AC 21 ms 892 KB
01_rnd_09.txt AC 21 ms 888 KB
02_maxrnd_00.txt AC 20 ms 920 KB
02_maxrnd_01.txt AC 20 ms 920 KB
02_maxrnd_02.txt AC 21 ms 860 KB
02_maxrnd_03.txt AC 21 ms 944 KB
02_maxrnd_04.txt AC 21 ms 912 KB
02_maxrnd_05.txt AC 22 ms 868 KB
02_maxrnd_06.txt AC 21 ms 916 KB
02_maxrnd_07.txt AC 21 ms 876 KB
02_maxrnd_08.txt AC 23 ms 884 KB
02_maxrnd_09.txt AC 21 ms 912 KB
02_maxrnd_10.txt AC 20 ms 916 KB
02_maxrnd_11.txt AC 20 ms 916 KB
02_maxrnd_12.txt AC 20 ms 912 KB
02_maxrnd_13.txt AC 22 ms 892 KB
02_maxrnd_14.txt AC 21 ms 864 KB
02_maxrnd_15.txt AC 21 ms 920 KB
02_maxrnd_16.txt AC 21 ms 916 KB
02_maxrnd_17.txt AC 21 ms 792 KB
02_maxrnd_18.txt AC 21 ms 920 KB
02_maxrnd_19.txt AC 21 ms 916 KB
03_increase_00.txt AC 21 ms 912 KB
03_increase_01.txt AC 21 ms 892 KB
03_increase_02.txt AC 21 ms 796 KB
04_decrease_00.txt AC 21 ms 912 KB
04_decrease_01.txt AC 21 ms 920 KB
04_decrease_02.txt AC 80 ms 916 KB
05_same_00.txt AC 20 ms 916 KB
05_same_01.txt AC 20 ms 920 KB