Submission #94335

#	Time	Username	Problem	Language	Result	Execution time	Memory
94335		zeyad49	Savez (COCI15_savez)	Java	48 / 120	292 ms	66560 KiB

savez

import java.io.*;
import java.util.*;

class savez{

	static int [][]memo;
	static int n;
	static int [][]hash;
	static int MOD=(int)1e9+9,p=31,pow[],maxN=(int)2e6+5;;
	//does i starts with last and end with last
	static boolean canTake(int i,int last) {
		if(last==n)
			return true;
		
		int n1=hash[i].length,n2=hash[last].length;
		if(n1<n2)
			return false;
		int compare=hash[last][n2-1];
		int prefix=hash[i][n2-1];
		int suffix=hash[i][n1-1]-(n1==n2?0:hash[i][n1-n2-1]);
		boolean ok=compare==prefix;
		if(n1>n2)
		{
			if(suffix<0)
				suffix+=MOD;
			compare=(int) (compare*1l*pow[n1-n2]%MOD);
		}
		ok&=compare==suffix;
		return ok;
	}
	static int dp(int last,int idx) {
		if(idx==n)
			return 0;
		if(memo[idx][last]!=-1)
			return memo[idx][last];
		int leave=dp(last,idx+1);
		int take=0;
		if(canTake(idx,last))
			take=dp(idx,idx+1)+1;
		return memo[idx][last]=Math.max(take, leave);
	}
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		PrintWriter out=new PrintWriter(System.out);
		pow=new int [maxN];
		pow[0]=1;
		for(int i=1;i<maxN;i++) {
			long x=pow[i-1]*1l*p%MOD;
			pow[i]=(int)x;
		}
		n=sc.nextInt();
		hash=new int [n][];
		memo=new int [n][n+1];
		for(int i=0;i<n;i++) {
			char []s=sc.next().toCharArray();
			int len=s.length;
			hash[i]=new int [len];
			Arrays.fill(memo[i], -1);
			long last=0;
			for(int j=0;j<len;j++) {
				last=last+(s[j]-'A'+1)*1l*pow[j];
				last%=MOD;
				hash[i][j]=(int)last;
			}
		}
		
		out.println(dp(n, 0));
		out.close();

	}
	
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		Scanner(String fileName) throws FileNotFoundException{
			br=new BufferedReader(new FileReader(fileName));
		}
		String next() throws IOException {
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		String nextLine() throws IOException {
			return br.readLine();
		}
		int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
		long nextLong()  throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12