DP Problem!

Правка en1, от quinamatics, 2017-09-05 03:17:39

Hello, I am working on the problem Duff In Beach for Codeforces Div 1 Round 326 getting WA on test case 4. I followed the editorial quite closely, so I think the issue might lie in not properly taking the modulus. Here is my WA code: import java.util.Arrays; import java.util.HashMap; import java.util.Scanner;

public class DuffInBeach { public static void main(String[] args) {

Scanner s = new Scanner(System.in);
String str = s.nextLine();
String[] strarr = str.split(" ");
int N = Integer.parseInt(strarr[0]);
double L = Double.parseDouble(strarr[1]);
int K = Integer.parseInt(strarr[2]);

long[][] dp = new long[N][K+1];
long[] a = new long[N];
str = s.nextLine();
strarr = str.split(" ");
HashMap hmap = new HashMap();
long[] b = new long[N];
//Index of sortings, a[p[i]]<= a[p[i+1]];
for(int i = 0; i < N; i++){
   a[i] = Long.parseLong(strarr[i]);
   b[i] = a[i];
   hmap.put(a[i], i);
}
Arrays.sort(b);
int[] p = new int[N];
for(int i = 0; i < N; i++)
   p[i] = (int) hmap.get(b[i]);
//# of permutations from Block 1 to Block J, for each pos I. 
for(int i = 0; i < dp.length; i++)
   dp[i][1] = 1;

for(int j = 2; j <= K; j++){
   for(int i = 0; i < N; i++){
     int ptr = 0;
     while(ptr < N && a[p[ptr]]<= a[i])
      dp[i][j] = (int) ((dp[i][j]+dp[p[ptr++]][j-1])%(1e9+7));
   }
}
Integer denom = new Integer(N);
long c = (long) Math.ceil(L/denom.doubleValue());
long min = Math.min(c, K);
int x = (int) ((L-1)%(N));

long ans = 0;
for(int i = 0; i <= x; i++){
   for(int j = 1; j <= min; j++){
     long sum = (long) ((dp[i][j]*(c-j+1))%(1e9+7));
     ans = (long) ((ans+sum)%(1e9+7));
   }
}
for(int i = x+1; i < N; i++){
   for(int j = 1; j <= Math.min(c-1,K); j++){
     long sum = (long)((dp[i][j]*(c-j)%(1e9+7)));
     ans = (long)((ans+sum)%(1e9+7));
   }
}
System.out.println(ans);

} }

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский quinamatics 2017-09-05 03:18:35 69
en1 Английский quinamatics 2017-09-05 03:17:39 2079 Initial revision (published)