Submission #1774651


Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;

public class Main{

	static PrintWriter out;
	static InputReader ir;

	static void solve(){
		int n=ir.nextInt(),MAX=(int)1e5;
		long MOD=(long)1e9+7;
		int[] d=ir.nextIntArray(n);
		long[][] dp=new long[MAX+1][4];
		for(int i=0;i<n;i++){
			dp[d[i]][3]++;
		}
		for(int i=1;i<=MAX;i++){
			dp[i][3]+=dp[i-1][3];
		}
		for(int j=2;j>=0;j--){
			for(int i=1;i<=MAX/2;i++){
				dp[i][j]=(dp[i][3]-dp[i-1][3])*(dp[MAX][j+1]-dp[i*2-1][j+1])%MOD;
			}
			for(int i=1;i<=MAX;i++){
					dp[i][j]+=dp[i-1][j];
					dp[i][j]%=MOD;
			}
		}
		out.println(dp[MAX][0]);
	}

	public static void main(String[] args) throws Exception{
		ir=new InputReader(System.in);
		out=new PrintWriter(System.out);
		solve();
		out.flush();
	}

	static class InputReader {

		private InputStream in;
		private byte[] buffer=new byte[1024];
		private int curbuf;
		private int lenbuf;

		public InputReader(InputStream in) {this.in=in; this.curbuf=this.lenbuf=0;}

		public boolean hasNextByte() {
			if(curbuf>=lenbuf){
				curbuf= 0;
				try{
					lenbuf=in.read(buffer);
				}catch(IOException e) {
					throw new InputMismatchException();
				}
				if(lenbuf<=0) return false;
			}
			return true;
		}

		private int readByte(){if(hasNextByte()) return buffer[curbuf++]; else return -1;}

		private boolean isSpaceChar(int c){return !(c>=33&&c<=126);}

		private void skip(){while(hasNextByte()&&isSpaceChar(buffer[curbuf])) curbuf++;}

		public boolean hasNext(){skip(); return hasNextByte();}

		public String next(){
			if(!hasNext()) throw new NoSuchElementException();
			StringBuilder sb=new StringBuilder();
			int b=readByte();
			while(!isSpaceChar(b)){
				sb.appendCodePoint(b);
				b=readByte();
			}
			return sb.toString();
		}

		public int nextInt() {
			if(!hasNext()) throw new NoSuchElementException();
			int c=readByte();
			while (isSpaceChar(c)) c=readByte();
			boolean minus=false;
			if (c=='-') {
				minus=true;
				c=readByte();
			}
			int res=0;
			do{
				if(c<'0'||c>'9') throw new InputMismatchException();
				res=res*10+c-'0';
				c=readByte();
			}while(!isSpaceChar(c));
			return (minus)?-res:res;
		}

		public long nextLong() {
			if(!hasNext()) throw new NoSuchElementException();
			int c=readByte();
			while (isSpaceChar(c)) c=readByte();
			boolean minus=false;
			if (c=='-') {
				minus=true;
				c=readByte();
			}
			long res = 0;
			do{
				if(c<'0'||c>'9') throw new InputMismatchException();
				res=res*10+c-'0';
				c=readByte();
			}while(!isSpaceChar(c));
			return (minus)?-res:res;
		}

		public double nextDouble(){return Double.parseDouble(next());}

		public int[] nextIntArray(int n){
			int[] a=new int[n];
			for(int i=0;i<n;i++) a[i]=nextInt();
			return a;
		}

		public long[] nextLongArray(int n){
			long[] a=new long[n];
			for(int i=0;i<n;i++) a[i]=nextLong();
			return a;
		}

		public char[][] nextCharMap(int n,int m){
			char[][] map=new char[n][m];
			for(int i=0;i<n;i++) map[i]=next().toCharArray();
			return map;
		}
	}
}

Submission Info

Submission Time
Task B - 難易度
User holeguma
Language Java8 (OpenJDK 1.8.0)
Score 50
Code Size 3284 Byte
Status WA
Exec Time 130 ms
Memory 28500 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 50 / 50 0 / 50
Status
AC × 3
AC × 22
AC × 42
WA × 1
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt
Case Name Status Exec Time Memory
sample_01.txt AC 90 ms 26452 KB
sample_02.txt AC 100 ms 25940 KB
sample_03.txt AC 101 ms 23764 KB
subtask1_01.txt AC 99 ms 26068 KB
subtask1_02.txt AC 93 ms 25044 KB
subtask1_03.txt AC 104 ms 25172 KB
subtask1_04.txt AC 105 ms 25940 KB
subtask1_05.txt AC 103 ms 20692 KB
subtask1_06.txt AC 103 ms 23636 KB
subtask1_07.txt AC 104 ms 25684 KB
subtask1_08.txt AC 104 ms 24788 KB
subtask1_09.txt AC 103 ms 28116 KB
subtask1_10.txt AC 102 ms 25428 KB
subtask1_11.txt AC 104 ms 24660 KB
subtask1_12.txt AC 105 ms 27476 KB
subtask1_13.txt AC 103 ms 22356 KB
subtask1_14.txt AC 103 ms 22740 KB
subtask1_15.txt AC 102 ms 24660 KB
subtask1_16.txt AC 103 ms 28116 KB
subtask1_17.txt AC 103 ms 24148 KB
subtask1_18.txt AC 103 ms 24404 KB
subtask1_19.txt AC 95 ms 24020 KB
subtask2_01.txt AC 115 ms 27600 KB
subtask2_02.txt AC 111 ms 22992 KB
subtask2_03.txt AC 108 ms 26836 KB
subtask2_04.txt AC 113 ms 26452 KB
subtask2_05.txt AC 110 ms 26708 KB
subtask2_06.txt AC 121 ms 27860 KB
subtask2_07.txt AC 106 ms 26452 KB
subtask2_08.txt AC 107 ms 26196 KB
subtask2_09.txt AC 120 ms 28240 KB
subtask2_10.txt AC 118 ms 26068 KB
subtask2_11.txt WA 109 ms 26068 KB
subtask2_12.txt AC 117 ms 28500 KB
subtask2_13.txt AC 113 ms 25556 KB
subtask2_14.txt AC 130 ms 25760 KB
subtask2_15.txt AC 123 ms 28116 KB
subtask2_16.txt AC 121 ms 28116 KB
subtask2_17.txt AC 121 ms 26708 KB
subtask2_18.txt AC 122 ms 27220 KB
subtask2_19.txt AC 121 ms 26452 KB
subtask2_20.txt AC 118 ms 26068 KB
subtask2_21.txt AC 106 ms 25684 KB