oj.uz

답안 #170599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170599 2019-12-25T18:18:33 Z manh9203 Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 14 ms 544 KB 
#include<bits/stdc++.h>
using namespace std;
long long t,l,r,dp[20][20][20][2];
string s;
long long solve(string s){
	if(s == "-1") return 0;
	int n = s.length(); 
	s = " " + s;
	memset(dp, 0, sizeof dp);
	dp[0][0][0][1] = 1;
	for(int i=1;i<=n;i++){
		int hah = (i == 1 ? 2 : 1);
		for(int cs = hah; cs <= 10; cs++){
			if(cs == s[i] - 47){
				for(int las = 0; las <= 10; las++){
					for(int pre = 0; pre <= 10; pre++){
						if(pre != cs && las != cs){
							dp[i][las][cs][1] += dp[i-1][pre][las][1];
						}
					}
				}
			}
			if(cs < s[i] - 47){
				for(int las = 0; las <= 10; las++){
					for(int pre = 0; pre <= 10; pre++){
						if(pre != cs && las != cs){
							dp[i][las][cs][0] += dp[i-1][pre][las][1];
						}
					}
				}
			}
			for(int las = 0; las <= 10; las++){
				for(int pre = 0; pre <= 10; pre++){
					if(pre != cs && las != cs){
						dp[i][las][cs][0] += dp[i-1][pre][las][0];
					}
				}
			}
			if(i > 1 && cs > 1){
				dp[i][0][cs][0]++;
			}
		}
	}
	long long ans = 1;
	for(int cs = 0; cs <= 10; cs++){
		for(int las = 0; las <= 10; las++){
			ans += dp[n][las][cs][1] + dp[n][las][cs][0];
		}
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> l >> r;
	l--; s = to_string(l);
	long long ans1 = solve(s);
	s = to_string(r);
	long long ans2 = solve(s);
	cout << ans2 - ans1;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 412 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 504 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 544 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 2 ms 404 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 2 ms 504 KB Output is correct
20 Correct 2 ms 504 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 504 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 412 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 508 KB Output is correct
19 Correct 2 ms 504 KB Output is correct
20 Correct 2 ms 504 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 2 ms 504 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 2 ms 508 KB Output is correct
26 Correct 2 ms 504 KB Output is correct
27 Correct 2 ms 504 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 504 KB Output is correct
30 Correct 2 ms 504 KB Output is correct
31 Correct 2 ms 504 KB Output is correct
32 Correct 14 ms 504 KB Output is correct
33 Correct 2 ms 504 KB Output is correct
34 Correct 2 ms 504 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 504 KB Output is correct
37 Correct 2 ms 504 KB Output is correct
38 Correct 2 ms 504 KB Output is correct
39 Correct 2 ms 380 KB Output is correct
40 Correct 2 ms 504 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 504 KB Output is correct
44 Correct 2 ms 504 KB Output is correct
45 Correct 2 ms 504 KB Output is correct