fork download
copy 
  1. import static java.lang.Double.parseDouble;
  2. import static java.lang.Integer.parseInt;
  3. import static java.lang.Long.parseLong;
  4. import static java.lang.Math.*;
  5. import static java.lang.System.exit;
  6.  
  7. import java.io.*;
  8. import java.util.*;
  9.  
  10.  class Ideone {
  11.  
  12.     static BufferedReader in;
  13.     static PrintWriter out;
  14.     static StringTokenizer tok;
  15.  
  16.  
  17.     class Pair implements Comparable<Pair> {
  18.         int r, l;
  19.  
  20.         Pair(int l, int r) {
  21.             this.l = l;
  22.             this.r = r;
  23.         }
  24.  
  25.         @Override
  26.         public int compareTo(Pair o) {
  27.             return l == o.l ? r - o.r : l - o.l;
  28.         }
  29.     }
  30.  
  31.     int n, q, dp[][][];
  32.     Pair segs[];
  33.     int fun(int i,int last, int missed) {
  34.         if(i == q) return missed == 2 ? 0 : -n;
  35.         if(dp[missed][i][last] != -1) return dp[missed][i][last];
  36.         int ans = 0;
  37.         if(missed < 2) ans = max(ans, fun(i+1, last, missed + 1));
  38.         if(last >= segs[i].l) {
  39.             ans = max(ans , max(segs[i].r - last, 0) + fun(i+1, max(last, segs[i].r), missed));
  40.         } else {
  41.             ans = max(ans , segs[i].r - segs[i].l + 1 + fun(i+1, max(last, segs[i].r), missed));
  42.         }
  43.         return dp[missed][i][last]=ans;
  44.     }
  45.  
  46.     void solve() throws Exception {
  47.         n = nextInt(); q = nextInt();
  48.         segs = new Pair[q];
  49.         for(int i = 0; i < q; i++) segs[i] = new Pair(nextInt(), nextInt());
  50.         Arrays.sort(segs);
  51.         dp = new int[3][5010][5010];
  52.         for(int i = 0; i < 3; i++) for(int j= 0; j < 5010;j++) Arrays.fill(dp[i][j], -1);
  53.         out.println(fun(0,0,0));
  54.     }
  55.  
  56.  
  57.     // call it like this: lower_bound(a, x + 1) ( /!\ + 1 )
  58.     public static int lower_bound(int[] a, int v) {
  59.         int low = -1, high = a.length;
  60.         while (high - low > 1) {
  61.             int h = high + low >>> 1;
  62.             if (a[h] >= v) {
  63.                 high = h;
  64.             } else {
  65.                 low = h;
  66.             }
  67.         }
  68.         return high;
  69.     }
  70.  
  71.     private int gcd(int a, int b) {
  72.         while (b > 0) {
  73.             int temp = b;
  74.             b = a % b;
  75.             a = temp;
  76.         }
  77.         return a;
  78.     }
  79.  
  80.     private int lcm(int a, int b) {
  81.         return a * (b / gcd(a, b));
  82.     }
  83.  
  84.     public static int[] radixSort(int[] f) {
  85.         int[] to = new int[f.length];
  86.         {
  87.             int[] b = new int[65537];
  88.             for (int i = 0; i < f.length; i++) b[1 + (f[i] & 0xffff)]++;
  89.             for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
  90.             for (int i = 0; i < f.length; i++) to[b[f[i] & 0xffff]++] = f[i];
  91.             int[] d = f;
  92.             f = to;
  93.             to = d;
  94.         }
  95.         {
  96.             int[] b = new int[65537];
  97.             for (int i = 0; i < f.length; i++) b[1 + (f[i] >>> 16)]++;
  98.             for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
  99.             for (int i = 0; i < f.length; i++) to[b[f[i] >>> 16]++] = f[i];
  100.             int[] d = f;
  101.             f = to;
  102.             to = d;
  103.         }
  104.         return f;
  105.     }
  106.  
  107.     private int[] na(int n) throws IOException {
  108.         int[] a = new int[n];
  109.         for (int i = 0; i < n; i++) a[i] = nextInt();
  110.         return a;
  111.     }
  112.  
  113.     private long[] nal(int n) throws IOException {
  114.         long[] a = new long[n];
  115.         for (int i = 0; i < n; i++) a[i] = nextLong();
  116.         return a;
  117.     }
  118.  
  119.     int nextInt() throws IOException {
  120.         return parseInt(next());
  121.     }
  122.  
  123.     long nextLong() throws IOException {
  124.         return parseLong(next());
  125.     }
  126.  
  127.     double nextDouble() throws IOException {
  128.         return parseDouble(next());
  129.     }
  130.  
  131.     String next() throws IOException {
  132.         while (tok == null || !tok.hasMoreTokens()) {
  133.             tok = new StringTokenizer(in.readLine());
  134.         }
  135.         return tok.nextToken();
  136.     }
  137.  
  138.     public static void main(String[] args) throws Exception {
  139.         try {
  140.             in = new BufferedReader(new InputStreamReader(System.in));
  141.             out = new PrintWriter(new OutputStreamWriter(System.out));
  142.             //long lStartTime = System.currentTimeMillis();
  143.             new Ideone().solve();
  144.             //long lEndTime = System.currentTimeMillis();
  145.             //out.println("Elapsed time in seconds: " + (double)(lEndTime - lStartTime) / 1000.0);
  146.             in.close();
  147.             out.close();
  148.         } catch (Throwable e) {
  149.             e.printStackTrace();
  150.             exit(1);
  151.         }
  152.     }
  153. }
Success #stdin #stdout 0.19s 2184192KB
comments (?)
stdin
copy 
7 5
1 4
4 5
5 6
6 7
3 5
stdout
copy 
7
https://ideone.com/nQ9nZG
language:
Java (HotSpot 12)
created:
5 years 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!