fork download
copy 
  1. import java.awt.Point;
  2. import java.io.BufferedReader;
  3. import java.io.FileReader;
  4. import java.io.FileWriter;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.io.PrintWriter;
  8. import java.math.BigInteger;
  9. import java.util.ArrayList;
  10. import java.util.Arrays;
  11. import java.util.Collections;
  12. import java.util.HashMap;
  13. import java.util.LinkedList;
  14. import java.util.Scanner;
  15. import java.util.Stack;
  16. import java.util.StringTokenizer;
  17.  
  18.  
  19.  
  20.  
  21.  
  22. class TestClass {
  23.  
  24. static long[] dis ;	
  25. static int[] vis;
  26. static ArrayList<Integer>[] resu;
  27. static int[] som;
  28. static long max;
  29. static long max2;
  30. static int[][] dp;
  31.  
  32. public static void update(int[] som , int i, int value){
  33.  
  34. while(i<=100000){
  35.  
  36. som[i]+=value;
  37. i+=(i&-i);
  38. }
  39. }
  40.  
  41. public static int value(int[] som , int i){
  42. int ans =0;
  43.  
  44. while(i>0)
  45. {
  46. ans+=som[i];
  47. i-=(i&-i);
  48.  
  49. }
  50. return ans;
  51.  
  52.  
  53. }
  54.  
  55.  
  56. public static void main(String args[] ) throws IOException {
  57.  
  58.  
  59. // BufferedReader in = new BufferedReader(new FileReader("C:\\Users\\Sompathak\\Desktop\\yes.txt"));
  60. // Scanner in = new Scanner(new FileReader("C:\\Users\\Sompathak\\Desktop\\yes.txt"));
  61. // PrintWriter pw = new PrintWriter(new FileWriter("C:\\Users\\Sompathak\\Desktop\\output.txt"));
  62.  
  63. Scanner in = new Scanner(new InputStreamReader(System.in));
  64. //Scanner in = new Scanner(new FileReader("C:\\Users\\Sompathak\\Desktop\\yes.txt"));
  65. int n = in.nextInt();
  66. int k =in.nextInt();
  67. int[] a = new int[n];
  68. for(int i=0;i<n;i++) a[i]=in.nextInt();
  69. som = new int[100001];
  70. dp = new int[n+1][k+1];
  71. for(int i=0;i<n;i++) dp[i][1]=1;
  72.  
  73. for(int i=2;i<=k;i++){
  74.  som = new int[100001];
  75. for(int j=1;j<n;j++){
  76.  
  77. int xx = dp[j-1][i-1];
  78. if(xx!=0)
  79. update(som,a[j-1],xx);
  80. dp[j][i] = value(som,a[j]-1);
  81. }
  82. }
  83. int ans =0;
  84. for(int i=0;i<n;i++) ans+=dp[i][k];
  85. System.out.println(ans);
  86.  
  87. }
  88. }
  89.  
Success #stdin #stdout 0.11s 380672KB
comments (?)
stdin
copy 
4 3
1
2
2
10
stdout
copy 
2
https://ideone.com/nEZstS
problem INCSEQ, based on SPOJ submission 13157984 (JAVA), 2014-12-13 19:49:11
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!