답안 #81575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
81575 2018-10-25T11:43:31 Z arman_ferdous Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
3 ms 944 KB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n, arr[20];
ll dp[20][2][2][11][11];

vector<ll> v;
ll DP(int pos, int s, int t, int f1, int f2) {
	if(pos >= n) return 1;
	if(dp[pos][s][t][f1][f2] != -1) return dp[pos][s][t][f1][f2];
	int bound = (t ? arr[pos] : 9);
	ll ret = 0;
	for(int i = 0; i <= bound; i++) {
		if(i == f1 || i == f2) continue;
		ret += DP(pos+1, (i==0 ? s : 1), (i<arr[pos] ? 0 : t), (i==0 && !s)?10:i , f1);
		//        next      started?           tight?           prev value      the one before
	}
	return dp[pos][s][t][f1][f2] = ret;
}

void apply(ll x) {
	n = log10(x) + 1;
	for(int i = n-1; i >= 0; i--) {
		arr[i] = x % 10;
		x /= 10;
	}
}

int main() {
	ll a, b;
	scanf("%lld %lld", &a, &b);

	if(b == 0) { puts("1"); return 0; }

	apply(b);
	memset(dp,-1,sizeof dp);
	ll ansr = DP(0,0,1,10,10);

	if(a == 1) { printf("%lld\n", ansr - 1); return 0; }
	if(a == 0) { printf("%lld\n", ansr);     return 0; }

	apply(a-1);
	memset(dp,-1,sizeof dp);
	ll ansl = DP(0,0,1,10,10);

	printf("%lld\n", ansr - ansl);
	return 0;
}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 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 504 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 2 ms 676 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 2 ms 752 KB Output is correct
12 Correct 2 ms 752 KB Output is correct
13 Correct 2 ms 752 KB Output is correct
14 Correct 2 ms 752 KB Output is correct
15 Correct 2 ms 752 KB Output is correct
16 Correct 2 ms 752 KB Output is correct
17 Correct 2 ms 752 KB Output is correct
18 Correct 2 ms 752 KB Output is correct
19 Correct 2 ms 752 KB Output is correct
20 Correct 2 ms 752 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 752 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 752 KB Output is correct
4 Correct 2 ms 752 KB Output is correct
5 Correct 2 ms 752 KB Output is correct
6 Correct 2 ms 752 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 2 ms 752 KB Output is correct
9 Correct 3 ms 752 KB Output is correct
10 Correct 3 ms 752 KB Output is correct
11 Correct 2 ms 756 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 2 ms 772 KB Output is correct
16 Correct 3 ms 776 KB Output is correct
17 Correct 2 ms 780 KB Output is correct
18 Correct 3 ms 784 KB Output is correct
19 Correct 2 ms 788 KB Output is correct
20 Correct 2 ms 792 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 3 ms 912 KB Output is correct
23 Correct 2 ms 912 KB Output is correct
24 Correct 2 ms 912 KB Output is correct
25 Correct 2 ms 912 KB Output is correct
26 Correct 2 ms 912 KB Output is correct
27 Correct 2 ms 912 KB Output is correct
28 Correct 2 ms 912 KB Output is correct
29 Correct 2 ms 912 KB Output is correct
30 Correct 2 ms 912 KB Output is correct
31 Correct 2 ms 912 KB Output is correct
32 Correct 2 ms 912 KB Output is correct
33 Correct 2 ms 912 KB Output is correct
34 Correct 2 ms 912 KB Output is correct
35 Correct 2 ms 912 KB Output is correct
36 Correct 2 ms 912 KB Output is correct
37 Correct 2 ms 912 KB Output is correct
38 Correct 2 ms 912 KB Output is correct
39 Correct 2 ms 912 KB Output is correct
40 Correct 3 ms 912 KB Output is correct
41 Correct 2 ms 912 KB Output is correct
42 Correct 2 ms 912 KB Output is correct
43 Correct 2 ms 944 KB Output is correct
44 Correct 2 ms 944 KB Output is correct
45 Correct 2 ms 944 KB Output is correct