oj.uz

Submission #94335

# Submission time Handle Problem Language Result Execution time Memory
94335 2019-01-17T18:14:23 Z zeyad49 Savez (COCI15_savez) Java 11
48 / 120
 292 ms 66560 KB 
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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 17876 KB Output is correct
2 Correct 146 ms 19236 KB Output is correct
3 Correct 149 ms 18612 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 19988 KB Output is correct
2 Correct 137 ms 17896 KB Output is correct
3 Correct 208 ms 24264 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 32708 KB Output is correct
2 Correct 287 ms 32356 KB Output is correct
3 Correct 290 ms 32308 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 22588 KB Output is correct
2 Correct 292 ms 32340 KB Output is correct
3 Correct 287 ms 33124 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 192 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 184 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 178 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 217 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 180 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 178 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -