fork download
copy 
  1.  
  2.     #include <bits/stdc++.h>
  3.  
  4.     using namespace std;
  5.  
  6.     using ll = long long;
  7.     const int MOD = 1000000007; 
  8.     const int MOD2 =  998244353; 
  9.     const ll INF = 1e18;
  10.     const int MX = 1000001; //check the limits, dummy
  11.  
  12.  
  13.     ll modExp(ll base, ll power) {
  14.         if (power == 0) {
  15.             return 1;
  16.         } else {
  17.             ll cur = modExp(base, power / 2); cur = cur * cur; cur = cur % MOD;
  18.             if (power % 2 == 1) cur = cur * base;
  19.             cur = cur % MOD;
  20.             return cur;
  21.         }
  22.     }
  23.  
  24.     ll inv(ll base) {
  25.         return modExp(base, MOD-2);
  26.     }
  27.  
  28.  
  29.     ll mul(ll A, ll B) {
  30.         return (A*B)%MOD;
  31.     }
  32.  
  33.     ll add(ll A, ll B) {
  34.         return (A+B)%MOD;
  35.     }
  36.  
  37.     ll dvd(ll A, ll B) {
  38.         return mul(A, inv(B));
  39.     }
  40.  
  41.     ll sub(ll A, ll B) {
  42.         return (A-B+MOD)%MOD;
  43.     }
  44.  
  45.     ll* facs = new ll[MX];
  46.     ll* facInvs = new ll[MX];
  47.  
  48.     ll choose(ll a, ll b) {
  49.         if (b > a) return 0;
  50.         if (a < 0) return 0;
  51.         if (b < 0) return 0;
  52.         ll cur = facs[a];
  53.         cur = mul(cur, facInvs[b]);
  54.         cur = mul(cur, facInvs[a-b]);
  55.         return cur;
  56.     }
  57.  
  58.     void initFacs() {
  59.         facs[0] = 1; 
  60.         facInvs[0] = 1;
  61.         for (int i = 1 ; i < MX ; i ++ ) {
  62.             facs[i] = (facs[i-1] * i) % MOD;
  63.             facInvs[i] = inv(facs[i]);
  64.         }
  65.     }
  66.     const int maxm = 4005; 
  67.     int n;
  68.     int id[maxm][maxm];
  69.     int dp[maxm][maxm];
  70.     int vis[maxm][maxm];
  71.     vector<int> gl[maxm];
  72.     int dfs(int l, int r) {
  73.         if (l >=r ) {
  74.             return 0;
  75.         }  
  76.         if (dp[l][r] != -1) {
  77.             return dp[l][r]; 
  78.         }
  79.         dp[l][r] = dfs(l + 1, r);
  80.         for (int nr : gl[l]) {
  81.             if (nr < r) {
  82.                 if (dp[l][r] < dfs(l,nr ) + 1 + dfs(nr,r)) {
  83.                     dp[l][r] = dfs(l,nr ) + 1 + dfs(nr,r); 
  84.                     vis[l][r] = nr; 
  85.                 } 
  86.             }
  87.         }
  88.  
  89.  
  90.         return dp[l][r] += (id[l][r] != -1 ? 1 : 0); 
  91.     }
  92.  
  93.     void output(int l , int r ) {
  94.         if (l <= r) {
  95.             return; 
  96.         }
  97.         if (id[l][r] != -1) {
  98.             cout << id[l][r] << ' ';  
  99.         } 
  100.         if (vis[l][r] == -1) {
  101.             output(l + 1, r);
  102.         } else{
  103.             cout << id[l][vis[l][r]] << ' ';
  104.             output(l,vis[l][r]);
  105.             output(vis[l][r],r);
  106.         }
  107.     }
  108.     int main()  {
  109.         ios_base::sync_with_stdio(0); cin.tie(0);  
  110.         cin >> n; 
  111.         memset(id, -1, sizeof(id)); 
  112.         memset(dp, -1, sizeof(dp)); 
  113.         memset(vis, -1, sizeof(vis)); 
  114.         int c = 0;
  115.         vector<int> s;
  116.         vector<pair<int,int>> p(n + 1);
  117.         for (int i = 1 ; i <= n; i ++) {
  118.             int c ,d ; cin >> c >> d;
  119.             int a =  c - d;
  120.             int  b = c + d; 
  121.             s.push_back(a);
  122.             s.push_back(b);
  123.             p[i].first = a;
  124.             p[i].second = b;
  125.         }
  126.         sort(s.begin() , s.end()); 
  127.         auto it = unique(s.begin(), s.end());
  128.         s.erase(it,s.end());
  129.         int u = s.size(); 
  130.         map<int,int> m;
  131.         for (int i = 1 ; i <= u  ; i ++) {
  132.             m[s[i - 1]] = i;  
  133.         }
  134.         for (int i = 1; i <= n; i ++) {
  135.             p[i - 1].first = m[p[i - 1].first];
  136.             p[i - 1].second= m[p[i - 1].second];
  137.             gl[p[i - 1].first].push_back(p[i - 1].second); 
  138.             id[p[i - 1].first][p[i - 1].second] = i; 
  139.         }
  140.  
  141.  
  142.         cout << dfs(1,u) << endl; 
  143.         output(1,u);
  144.         return 0;
  145.     }
  146.  
Success #stdin #stdout 0.04s 191652KB
comments (?)
stdin
copy 
4
1 1
2 2
4 1
5 1
stdout
copy 
5
https://ideone.com/u9wqXX
language:
C++ (gcc 8.3)
created:
14 days 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!