Submission #3219684
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; class Main{ static void solve(){ int n = ni(); int[] x = nia(n); long mod = (long) 1e9+7; long[] dp = new long[n]; dp[0]=1; int mink = -1; for(int i=1;i<n;++i){ if(x[i-1] - 2*i>=mink){ dp[i]=dp[i-1]+1; } else{ dp[i]=dp[i-1]; mink=-2*i; } mink = Math.min(mink, x[i-1]-2*i); } for(int i=1;i<n;++i)dp[i]=(dp[i]*dp[i-1])%mod; out.println(dp[n-1]); } public static void main(String[] args){ solve(); out.flush(); } private static InputStream in = System.in; private static PrintWriter out = new PrintWriter(System.out); static boolean inrange(int y, int x, int h, int w){ return y>=0 && y<h && x>=0 && x<w; } @SuppressWarnings("unchecked") static<T extends Comparable> int lower_bound(List<T> list, T key){ int lower=-1;int upper=list.size(); while(upper - lower>1){ int center =(upper+lower)/2; if(list.get(center).compareTo(key)>=0)upper=center; else lower=center; } return upper; } @SuppressWarnings("unchecked") static <T extends Comparable> int upper_bound(List<T> list, T key){ int lower=-1;int upper=list.size(); while(upper-lower >1){ int center=(upper+lower)/2; if(list.get(center).compareTo(key)>0)upper=center; else lower=center; } return upper; } @SuppressWarnings("unchecked") static <T extends Comparable> boolean next_permutation(List<T> list){ int lastIndex = list.size()-2; while(lastIndex>=0 && list.get(lastIndex).compareTo(list.get(lastIndex+1))>=0)--lastIndex; if(lastIndex<0)return false; int swapIndex = list.size()-1; while(list.get(lastIndex).compareTo(list.get(swapIndex))>=0)swapIndex--; T tmp = list.get(lastIndex); list.set(lastIndex++, list.get(swapIndex)); list.set(swapIndex, tmp); swapIndex = list.size()-1; while(lastIndex<swapIndex){ tmp = list.get(lastIndex); list.set(lastIndex, list.get(swapIndex)); list.set(swapIndex, tmp); ++lastIndex;--swapIndex; } return true; } private static final byte[] buffer = new byte[1<<15]; private static int ptr = 0; private static int buflen = 0; private static boolean hasNextByte(){ if(ptr<buflen)return true; ptr = 0; try{ buflen = in.read(buffer); } catch (IOException e){ e.printStackTrace(); } return buflen>0; } private static int readByte(){ if(hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isSpaceChar(int c){ return !(33<=c && c<=126);} private static int skip(){int res; while((res=readByte())!=-1 && isSpaceChar(res)); return res;} private static double nd(){ return Double.parseDouble(ns()); } private static char nc(){ return (char)skip(); } private static String ns(){ StringBuilder sb = new StringBuilder(); for(int b=skip();!isSpaceChar(b);b=readByte())sb.append((char)b); return sb.toString(); } private static int[] nia(int n){ int[] res = new int[n]; for(int i=0;i<n;++i)res[i]=ni(); return res; } private static long[] nla(int n){ long[] res = new long[n]; for(int i=0;i<n;++i)res[i]=nl(); return res; } private static int ni(){ int res=0,b; boolean minus=false; while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); if(b=='-'){ minus=true; b=readByte(); } for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); return minus ? -res:res; } private static long nl(){ long res=0,b; boolean minus=false; while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); if(b=='-'){ minus=true; b=readByte(); } for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); return minus ? -res:res; } }
Submission Info
Submission Time | |
---|---|
Task | A - Robot Racing |
User | inmir |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 4004 Byte |
Status | WA |
Exec Time | 97 ms |
Memory | 22484 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 500 | 0 / 400 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
Subtask | 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 68 ms | 21204 KB |
0_01.txt | AC | 69 ms | 19156 KB |
0_02.txt | AC | 68 ms | 18132 KB |
0_03.txt | AC | 68 ms | 20692 KB |
1_00.txt | AC | 67 ms | 18132 KB |
1_01.txt | AC | 70 ms | 20052 KB |
1_02.txt | AC | 68 ms | 17364 KB |
1_03.txt | WA | 69 ms | 17876 KB |
1_04.txt | AC | 68 ms | 21204 KB |
1_05.txt | AC | 70 ms | 20180 KB |
1_06.txt | WA | 69 ms | 17748 KB |
1_07.txt | AC | 69 ms | 19156 KB |
1_08.txt | AC | 68 ms | 19284 KB |
1_09.txt | AC | 69 ms | 19156 KB |
1_10.txt | AC | 70 ms | 22484 KB |
2_00.txt | WA | 88 ms | 21204 KB |
2_01.txt | AC | 97 ms | 21716 KB |
2_02.txt | AC | 91 ms | 19540 KB |
2_03.txt | WA | 89 ms | 19156 KB |
2_04.txt | WA | 93 ms | 19796 KB |
2_05.txt | WA | 90 ms | 21716 KB |
2_06.txt | WA | 88 ms | 18516 KB |
2_07.txt | WA | 91 ms | 18644 KB |
2_08.txt | WA | 92 ms | 17748 KB |
2_09.txt | WA | 89 ms | 17620 KB |
2_10.txt | WA | 93 ms | 18260 KB |
2_11.txt | AC | 95 ms | 21332 KB |
2_12.txt | AC | 93 ms | 21588 KB |