fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define pi pair<int,int>
  6.  
  7. const int N = 305;
  8. const int INF = 1e18;
  9.  
  10. int m;
  11. pi p[N];
  12. int dp[N], cnt[N];
  13.  
  14. signed main(){
  15.     ios::sync_with_stdio(false);
  16.     cin.tie(nullptr);
  17.  
  18.     cin >> m;
  19.     for(int i = 1; i <= m; i++){
  20.         cin >> p[i].first >> p[i].second;
  21.         if(p[i].first > p[i].second)
  22.             swap(p[i].first, p[i].second);
  23.     }
  24.  
  25.     sort(p + 1, p + m + 1, [](pi a, pi b){
  26.         return a.second < b.second;
  27.     });
  28.  
  29.     int mx = 0;
  30.     for(int i = 1; i <= m; i++){
  31.         dp[i] = 1;
  32.         cnt[i] = 1;
  33.         for(int j = 1; j < i; j++){
  34.             if(p[j].second <= p[i].first){
  35.                 if(dp[j] + 1 > dp[i]){
  36.                     dp[i] = dp[j] + 1;
  37.                     cnt[i] = cnt[j];
  38.                 }
  39.                 else if(dp[j] + 1 == dp[i]){
  40.                     cnt[i] += cnt[j];
  41.                 }
  42.             }
  43.         }
  44.         mx = max(mx, dp[i]);
  45.     }
  46.  
  47.     int ways = 0;
  48.     for(int i = 1; i <= m; i++){
  49.         if(dp[i] == mx)
  50.             ways += cnt[i];
  51.     }
  52.  
  53.     cout << m - mx << " " << ways;
  54.     return 0;
  55. }
  56.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
5
1 3
3 5
4 6
8 9
4 6
stdout
copy 
2 3
https://ideone.com/Sl2L6P
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!