fork download
copy 
  1. #include <vector>
  2. #include <cassert>
  3. #include <list>
  4. #include <map>
  5. #include <set>
  6. #include <queue>
  7. #include <deque>
  8. #include <stack>
  9. #include <bitset>
  10. #include <algorithm>
  11. #include <functional>
  12. #include <numeric>
  13. #include <utility>
  14. #include <sstream>
  15. #include <iostream>
  16. #include <iomanip>
  17. #include <cstdio>
  18. #include <cmath>
  19. #include <cstdlib>
  20. #include <ctime>
  21. #include <cstring>
  22. #include <climits>
  23. #include <fstream>
  24. #include <sstream>
  25. #include<ctype.h>
  26.  
  27. #define PI 3.1415926535897932384626433832795028841971693993751058209749Lf
  28. #define INF 2000000000
  29. #define INFI 1e37
  30. #define pb push_back
  31. #define PRINT(x)           cout << #x << "  " << x << endl
  32. #define MAX ((int)1e6+10)
  33. #define MOD 1000000007
  34. #define BUF 4096
  35.  
  36. char ibuf[BUF];
  37. int ipt = BUF;
  38.  
  39. int readInt() {
  40. 	while (ipt < BUF && ibuf[ipt] < '0') ipt++;
  41. 	if (ipt == BUF) {
  42. 		fread(ibuf, 1, BUF, stdin);
  43. 		ipt = 0;
  44. 		while (ipt < BUF && ibuf[ipt] < '0') ipt++;
  45. 	}
  46. 	int n = 0;
  47. 	while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
  48. 	if (ipt == BUF) {
  49. 		fread(ibuf, 1, BUF, stdin);
  50. 		ipt = 0;
  51. 		while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
  52. 	}
  53. 	return n;
  54. }
  55.  
  56. int main() {
  57.  
  58. 	long n,m;
  59.  
  60. 	n=readInt();
  61. 	m=readInt();
  62.  
  63. 	long a[n];
  64. 	long long dp[n]; //stores min number of stops from ith stop to destination.
  65. 	long long ways[n]; // Number of ways to reach destination from position i.
  66.  
  67. 	for(int i=0;i<n;i++) {a[i]=readInt(); dp[i]=ways[i]=0;}
  68.  
  69. 	dp[n-1]=0;
  70.  
  71. 	int i=n-1;int j=n-2;
  72.  
  73. 	while(j>=0)
  74. 	{
  75. 		if(a[i]-a[j]<=m) {dp[j]=(1+dp[i])%MOD; j--;}
  76. 		else {i=j+1;}
  77. 	}
  78.  
  79. 	ways[n-1]=0;
  80. 	j=n-2;int k=0;
  81.  
  82.  
  83. 	while(j>=0)
  84. 	{
  85.  		if(dp[j]==1) {ways[j]=1; j--; continue;}
  86.  		else
  87.  		{
  88.  		     k=j+1;
  89.  		     while(k<n && dp[j]-dp[k]<=1 && a[k]-a[j]<=m)
  90.  		     {
  91.  		     	if(dp[j]-dp[k]==1) // Add ways if difference in number of steps is 1.
  92.  		     	{
  93.  		     	  ways[j]=(ways[j]+ways[k])%MOD;
  94.  		     	}
  95.  		        k++;
  96.  		     }
  97.  		}
  98.  		j--;
  99. 	}
  100.  
  101. 	printf("%lld %lld",dp[0]-1,ways[0]);
  102. 	return 0;
  103. }
Success #stdin #stdout 0s 4340KB
comments (?)
stdin
copy 
6 3
0
1
3
4
7
10
stdout
copy 
3 2
https://ideone.com/ZgA0yr
language:
C++ (gcc 8.3)
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!