Submission #849146

#	Time	Username	Problem	Language	Result	Execution time	Memory
849146		tch1cherin	Boat (APIO16_boat)	C++17	9 / 100	1 ms	504 KiB

boat

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

const int MOD = 1e9 + 7;

void norm(int& X) {
  X -= X >= MOD ? MOD : 0;
}

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int &v : A) {
    cin >> v >> v;
  }
  vector<int> dp(N + 1);
  dp[0] = 1;
  for (int i = 0; i < N; i++)
    for (int j = i; j >= 0; j--)
      if (j == 0 || A[i] > A[j - 1])
        norm(dp[i + 1] += dp[j]);
  
  int ans = 0;
  for (int i = 1; i <= N; i++) {
    norm(ans += dp[i]);
  }
  cout << ans << "\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42