답안 #939032

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939032 2024-03-06T03:51:14 Z tamir1 Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
1 ms 804 KB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,dp[20][180][2][2][2];
vector<ll> v;
void build(ll a){
	if(a<10){
		v.push_back(a);
		return;
	}
	build(a/10);
	v.push_back(a%10);
}
ll rec(ll idx,ll sum,ll t,ll s,ll u,ll last1,ll last2){
	if(idx==v.size()) return 1;
	if(dp[idx][sum][t][s][u]!=-1) return dp[idx][sum][t][s][u];
	ll i,up=9,ans=0;
	if(!t) up=v[idx];
	for(i=0;i<=up;i++){
		if(s && last2==i) continue;
		if(u && last1==i) continue;
		ans+=rec(idx+1,sum+i,t|(i<up),s|(i>0),u|s,last2,i);
	}
	return dp[idx][sum][t][s][u]=ans;
}
ll solve(ll a){
	if(a==-1) return 0;
	v.clear();
	build(a);
	memset(dp,-1,sizeof dp);
	return rec(0,0,0,0,0,0,0);
}
int main(){
	cin >> a >> b;
	cout << solve(b)-solve(a-1);
}

Compilation message

numbers.cpp: In function 'long long int rec(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
numbers.cpp:15:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  if(idx==v.size()) return 1;
      |     ~~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 440 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 0 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 448 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 616 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 444 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 444 KB Output is correct
22 Correct 1 ms 804 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 0 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 0 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 0 ms 444 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 604 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Correct 1 ms 600 KB Output is correct
44 Correct 1 ms 604 KB Output is correct
45 Correct 1 ms 604 KB Output is correct