답안 #939032

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
939032	2024-03-06T03:51:14 Z	tamir1	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	804 KB

numbers

#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;
      |     ~~~^~~~~~~~~~

Subtask #1

25.0 / 25.0

#	결과	실행 시간	메모리	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

Subtask #2

75.0 / 75.0

#	결과	실행 시간	메모리	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