답안 #99743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99743	2019-03-06T15:06:11 Z	nandonathaniel	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	4 ms	568 KB

numbers

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL memo[20][11][11][2][2][2];

string s[2];

LL DP(LL digit_ke,LL last1,LL last2,LL flag,LL kata,LL tzero){    
    if(digit_ke>=s[kata].length())return 1;
    if(memo[digit_ke][last1][last2][flag][kata][tzero]!=-1)return memo[digit_ke][last1][last2][flag][kata][tzero];
    LL ans=0;
    if(flag==1){
		if(tzero==1){
			if(s[kata][digit_ke]=='0')ans+=DP(digit_ke+1,10,last1,1,kata,1);
			else ans+=DP(digit_ke+1,(LL)(s[kata][digit_ke]-'0'),last1,1,kata,0);
		}
		else{
			if((LL)(s[kata][digit_ke]-'0')!=last1 && (LL)(s[kata][digit_ke]-'0')!=last2)ans+=DP(digit_ke+1,(LL)(s[kata][digit_ke]-'0'),last1,1,kata,0);
		}
        for(LL dig=0;dig<(LL)(s[kata][digit_ke]-'0');dig++){
			if(tzero==1){
				if(dig==0)ans+=DP(digit_ke+1,10,last1,0,kata,1);
				else ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
			else{
				if(dig!=last1 && dig!=last2)ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
            
        }
    }
    else{
        for(LL dig=0;dig<=9;dig++){
			if(tzero==1){
				if(dig==0)ans+=DP(digit_ke+1,10,last1,0,kata,1);
				else ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
			else{
				if(dig!=last1 && dig!=last2)ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
            
        }
    }

    return memo[digit_ke][last1][last2][flag][kata][tzero]=ans;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	memset(memo,-1,sizeof(memo));
	LL L,res2;
	cin >> L >> s[1];
	LL res1=DP(0,10,10,1,1,1);
	if(L==0)res2=0;
	else{
		L--;
		s[0]=to_string(L);
		res2=DP(0,10,10,1,0,1);
	}
	//cout << res1 << " " << res2  << endl;
	cout << res1-res2 << endl;
	return 0;
}

Compilation message

numbers.cpp: In function 'LL DP(LL, LL, LL, LL, LL, LL)':
numbers.cpp:9:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(digit_ke>=s[kata].length())return 1;
        ~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1

25.0 / 25.0

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

Subtask #2

75.0 / 75.0

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