Submission #1210322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210322		sunflower	Exam (eJOI20_exam)	C++17	12 / 100	11 ms	1096 KiB

exam

#include <bits/stdc++.h>
using namespace std;

#define BIT(x, i) (((x) >> (i)) & 1)

template <class X, class Y>
  bool maximize(X &x, Y y) {
    if (x < y) return x = y, true;
    else return false;
  }

const int inf = (int) 1e9 + 7;

int n;

#define MAX_N 100'100
int a[MAX_N + 2], b[MAX_N + 2];

#undef MAX_N

namespace subtask2 {
  bool check() {
    return (*max_element(b + 1, b + 1 + n) == *min_element(b + 1, b + 1 + n));
  }

  void solve() {
    int ans = 0, cnt = 0;
    bool ok = false;
    a[n + 1] = inf;
    for (int i = 1; i <= n + 1; ++i) {
      if (a[i] > b[1]) {
        if (ok) ans += cnt;
        cnt = 0;
        ok = false;
      } else {
        ++cnt;
        if (a[i] == b[1]) ok = true;
      }
    }

    cout << ans;
  }
};

namespace subtask3 {
  bool check() {
    for (int i = 1; i < n; ++i) {
      if (a[i] >= a[i + 1]) return false;
    }
    return (n <= 5000);
  }

  int dp[5050];

  int cost[5050][5050];

  void solve() {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        cost[j][i] = cost[j - 1][i] + (a[i] == b[j]);
      }
    }

    for (int i = 1; i <= n; ++i) {
      dp[i] = dp[i - 1];
      for (int j = i; j >= 1; --j) {
        maximize(dp[i], dp[j - 1] + cost[i][i] - cost[j - 1][i]);
      }
    }

    cout << dp[n];
  }
};

namespace subtask1 {
  bool check() {
    return (n <= 10);
  }

  int c[20];

  void solve() {
    int ans = 0;
    for (int mask = 0; mask < (1 << n); ++mask) {
      for (int i = 0; i < n; ++i) {
        int r = i;
        for (int j = i + 1; j < n; ++j) if (BIT(mask, j) == BIT(mask, i)) r = j;
        else break;

        int tmp = 0;
        for (int j = i; j <= r; ++j) maximize(tmp, a[j + 1]);

        for (int j = i; j <= r; ++j) c[j + 1] = tmp;

        i = r;
      }

      int cnt = 0;
      for (int i = 1; i <= n; ++i) if (c[i] == b[i]) ++cnt;

      maximize(ans, cnt);
    }

    cout << ans;
  }
};

int main() {
  ios_base::sync_with_stdio(false);cin.tie(nullptr);
  if (fopen("test.inp","r")) {
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) cin >> b[i];

  if (subtask1 :: check()) return subtask1 :: solve(), 0;
  if (subtask2 :: check()) return subtask2 :: solve(), 0;
  if (subtask3 :: check()) return subtask3 :: solve(), 0;

  return 0;
}

Compilation message (stderr)

exam.cpp: In function 'int main()':
exam.cpp:111:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     freopen("test.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
exam.cpp:112:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     freopen("test.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22