http://codeforces.com/contest/834

It‘s the end of July – the time when a festive evening is held at Jelly Castle! Guests from all over the kingdom gather here to discuss new trends in the world of confectionery. Yet some of the things discussed here are not supposed to be disclosed to the general public: the information can cause discord in the kingdom of Sweetland in case it turns out to reach the wrong hands. So it‘s a necessity to not let any uninvited guests in.

There are 26 entrances in Jelly Castle, enumerated with uppercase English letters from A to Z. Because of security measures, each guest is known to be assigned an entrance he should enter the castle through. The door of each entrance is opened right before the first guest‘s arrival and closed right after the arrival of the last guest that should enter the castle through this entrance. No two guests can enter the castle simultaneously.

For an entrance to be protected from possible intrusion, a candy guard should be assigned to it. There are k such guards in the castle, so if there are more than k opened doors, one of them is going to be left unguarded! Notice that a guard can‘t leave his post until the door he is assigned to is closed.

Slastyona had a suspicion that there could be uninvited guests at the evening. She knows the order in which the invited guests entered the castle, and wants you to help her check whether there was a moment when more than k doors were opened.

Two integers are given in the first string: the number of guests n and the number of guards k (1?≤?n?≤?106, 1?≤?k?≤?26).

In the second string, n uppercase English letters s1s2... sn are given, where si is the entrance used by the i-th guest.

Output ?YES? if at least one door was unguarded during some time, and ?NO? otherwise.

You can output each letter in arbitrary case (upper or lower).

In the first sample case, the door A is opened right before the first guest‘s arrival and closed when the second guest enters the castle. The door B is opened right before the arrival of the third guest, and closed after the fifth one arrives. One guard can handle both doors, as the first one is closed before the second one is opened.

In the second sample case, the door B is opened before the second guest‘s arrival, but the only guard can‘t leave the door A unattended, as there is still one more guest that should enter the castle through this door.

 题意：有26个们和K个门卫，给你入场顺序，看是否有某个时候至少有一扇门没有守卫；

题解：找到没扇门关闭的最后时刻然后模拟；

#include
#include
#include 
#include
#include 
#include
#include#define ld long double
#define ll long long
const int inf=0x3f3f3f3f; 
const int maxn=1e6+5; 
using namespace std;
char a[maxn];
int b[27];
bool vis[27];
int n,k;
int main()
{
    scanf("%d %d",&n,&k);
    scanf("%s",a);
    for(int i=0;i)
    {
        b[a[i]-‘A‘]=i;
    }
    bool flag=true;
    for(int i=0;i)
    {
        if(!vis[a[i]-‘A‘])
        {
            k--;
            vis[a[i]-‘A‘]=true;
            if(k0)
            {
                flag=false;break;
            }
            if(i==b[a[i]-‘A‘])k++;
        }
        else if(i==b[a[i]-‘A‘])
        {
            k++;
        }
    }
    if(flag)puts("NO");
    else puts("YES");
}

C. The Meaningless Game

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Slastyona and her loyal dog Pushok are playing a meaningless game that is indeed very interesting.

The game consists of multiple rounds. Its rules are very simple: in each round, a natural number k is chosen. Then, the one who says (or barks) it faster than the other wins the round. After that, the winner‘s score is multiplied by k2, and the loser‘s score is multiplied by k. In the beginning of the game, both Slastyona and Pushok have scores equal to one.

Unfortunately, Slastyona had lost her notepad where the history of all n games was recorded. She managed to recall the final results for each games, though, but all of her memories of them are vague. Help Slastyona verify their correctness, or, to put it another way, for each given pair of scores determine whether it was possible for a game to finish with such result or not.

Input

In the first string, the number of games n (1?≤?n?≤?350000) is given.

Each game is represented by a pair of scores a, b (1?≤?a,?b?≤?109) – the results of Slastyona and Pushok, correspondingly.

Output

For each pair of scores, answer "Yes" if it‘s possible for a game to finish with given score, and "No" otherwise.

You can output each letter in arbitrary case (upper or lower).

Example

input

6
2 4
75 45
8 8
16 16
247 994
1000000000 1000000

output

Yes
Yes
Yes
No
No
Yes

Note

First game might have been consisted of one round, in which the number 2 would have been chosen and Pushok would have won.

The second game needs exactly two rounds to finish with such result: in the first one, Slastyona would have said the number 5, and in the second one, Pushok would have barked the number 3.

 题意：玩游戏，开始是都是1，每轮选一个数k,一个乘k，另一个乘k^2，；给a，b两个数，看是否是某个游戏的结果；

题解：比赛当时没想用二分去找，分解因数超时了。只要a*b==x^3&&(a/x)*(b/x)==x就可以了；

#include
#include
#include 
#include
#include 
#include
#include#define ld long double
#define ll long long
const int inf=0x3f3f3f3f; 
const int maxn=1e6+5; 
const ll N=1e18; 
using namespace std;
ll num[maxn]; 
int n;
ll x,y;
ll slove(ll l,ll r,ll m)
{
    while(lr)
    {
        ll mid=(l+r)>>1; 
        if(num[mid]==m)return mid; 
        else if(num[mid]>m)
        {
            r=mid-1; 
        }
        else
        {
            l=mid+1; 
        } 
    //    cout
    }
    return -1;    
}
int main()
{
    scanf("%d",&n);
    ll cnt; 
    for(cnt=1;cnt*cnt*cnt)
    num[cnt]=cnt*cnt*cnt; 
    while(n--)
    {
        scanf("%I64d %I64d",&x,&y);
         ll ans=slove(1,cnt-1,x*y); 
        if((x/ans)*(y/ans)==ans)
        {
            puts("Yes");
        }
        else
        {
            puts("No");
        }
    }
    return 0;
}

D. The Bakery

time limit per test

2.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Some time ago Slastyona the Sweetmaid decided to open her own bakery! She bought required ingredients and a wonder-oven which can bake several types of cakes, and opened the bakery.

Soon the expenses started to overcome the income, so Slastyona decided to study the sweets market. She learned it‘s profitable to pack cakes in boxes, and that the more distinct cake types a box contains (let‘s denote this number as the value of the box), the higher price it has.

She needs to change the production technology! The problem is that the oven chooses the cake types on its own and Slastyona can‘t affect it. However, she knows the types and order of n cakes the oven is going to bake today. Slastyona has to pack exactly k boxes with cakes today, and she has to put in each box several (at least one) cakes the oven produced one right after another (in other words, she has to put in a box a continuous segment of cakes).

Slastyona wants to maximize the total value of all boxes with cakes. Help her determine this maximum possible total value.

Input

The first line contains two integers n and k (1?≤?n?≤?35000, 1?≤?k?≤?min(n,?50)) – the number of cakes and the number of boxes, respectively.

The second line contains n integers a1,?a2,?...,?an (1?≤?ai?≤?n) – the types of cakes in the order the oven bakes them.

Output

Print the only integer – the maximum total value of all boxes with cakes.

Examples

input

4 1
1 2 2 1

output

2

input

7 2
1 3 3 1 4 4 4

output

5

input

8 3
7 7 8 7 7 8 1 7

output

6

Note

In the first example Slastyona has only one box. She has to put all cakes in it, so that there are two types of cakes in the box, so the value is equal to 2.

In the second example it is profitable to put the first two cakes in the first box, and all the rest in the second. There are two distinct types in the first box, and three in the second box then, so the total value is 5.

 

 题意：给你一个序列，分成K段让求每一段不同的数的数目的和最大

题解：最开始想简单了，用set贪心去做到后面发现不对，这题正确解法是dp+线段树，dp[i][j]表示分成i段在j的最大值，转移方程dp[i][j]=max(dp[i-1][j])0

我们用last[i]代表a[i]上次出现的位置，然后每次对last[i]~i的位置全加1，代码如下

#include
#include
#include 
#include
#include 
#include
#include#define ld long double
#define ll long long
using namespace std;
const int maxn=4e4+5e3+5; 
int n,k; 
int a[maxn];
int now[maxn],last[maxn]; 
int add[maxn2]; 
int dp[55][maxn]; 
int tree[maxn2]; 
void push(int rt)
{
    tree[rt]=max(tree[rt1],tree[rt1|1]);
    return; 
} 
void push_down(int rt)
{
    if(add[rt])
    {
        add[rt1]+=add[rt];
        add[rt1|1]+=add[rt];
        tree[rt1]+=add[rt];
        tree[rt1|1]+=add[rt];
        add[rt]=0; 
    } 
    return ; 
} 
void update(int L,int R,int c,int l,int r,int rt)
{
    if(LR)
    {
        tree[rt]+=c; 
        add[rt]+=c;
        return ; 
    } 
    push_down(rt); 
    int m=(l+r)/2;
    if(Lm)
    update(L,R,c,l,m,rt1);
    if(R>m)
    update(L,R,c,m+1,r,rt1|1);
    push(rt); 
    return ; 
} 
int query(int L,int R,int l,int r,int rt)
{
    if(LR)
    {
        return tree[rt]; 
    } 
    push_down(rt);
    int m=(l+r)>>1;
    int ans=0; 
    if(R>m)
        ans=max(ans,query(L,R,m+1,r,rt1|1));
    if(Lm)
        ans=max(ans,query(L,R,l,m,rt1));
    return ans;  
} 
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i)
    {
        scanf("%d",&a[i]); 
    }
    for(int i=1;i)
    {
        last[i]=now[a[i]];
        now[a[i]]=i; 
    }
    for(int i=1;i)
    {
        memset(tree,0,sizeof(tree));
        memset(add,0,sizeof(add)); 
        for(int j=1;j)
        {
            update(j,j,dp[i-1][j],0,n,1); 
        } 
        for(int j=i;j)
        {
            update(max(i-1,last[j]),j-1,1,0,n,1);
            dp[i][j]=query(i-1,j-1,0,n,1); 
        } 
    } 
    printf("%d\n",dp[k][n]); 
    return 0;