poj 객 잔 선택

소비 조건 에 맞 는 카페 를 찾 을 때마다 불법 으로 계산한다.OAAAAOAAOOAAOOAAAA 는 O 로 소비 수준 에 맞 는 카페 (객 잔) 를 대표 하고 A 는 특정한 색깔 의 객 잔 을 대표 한다.예전 에 7 개의 객 잔 을 예 로 들 면 두 개의 O 이전의 5 개의 객 잔 은 두 개의 선택 이 모두 비합법적 인 선택 방식, 즉 C (5, 2) 의 비합법적 인 방식 이 었 다.여기에 모두 16 개의 A 색 의 객 잔 이 있다 고 가정 하면 (이곳 의 16 은 O 중 색상 이 A 인 개 수 를 포함 하고 있 음 을 주의 하 세 요) 이곳 의 총 방법 수 는 C (16, 2) 이 고 합 법 수 는 C (16, 2) - C (5, 2) - C (2, 2) - C (4, 2) 입 니 다. 각 색상 을 나 누 어 고려 한 다음 에 합치 면 됩 니 다.

/**
4G:    
           
     : 1000ms     : 65535kB
  
      n         ，           1  n   。                （   k  ，    0 ~ k-1   ） ，             ，    
          。
           ，         ，           ，                  。  ，              ，                
 （        ） ，             p。
                  ，                  p        。

  
        n，k，p，              ，         ，                  ；
     n ，  i+1      ，         ，     i           i             。
  
      ，    ，            。
    
5 2 3
0 5
1 3
0 2
1 4
1 5
    
3
  
2           ，           ：   ①③，②④，②⑤，④⑤，
       4、5      ，4、5                 4，             3  ，       。      3      。


【    】
   30%   ，  n ≤ 100；
   50%   ，  n ≤ 1,000；
   100%   ，  2 ≤ n≤ 200,000，0 < k ≤ 50，0 ≤ p ≤ 100， 0 ≤      ≤ 100。
*/

#include <cstdio>
#include <cstdlib>
using namespace std;

int n = 0, k = 0, p = 0;
int color[200005] = {0}, cost[200005] = {0};
int dp[200005][51] = {0};


int c(int m)
{
    return m * (m - 1) / 2;
}

int main()
{
    int sumn[51] = {0};
    int sum_temp[51] = {0};
    int sum_illegal = 0;//       
    int sum_total = 0;//    
    scanf("%d%d%d", &n, &k, &p);
    //int mark = 0;
    for(int i = 0; i < n; ++i)
    {
        scanf("%d%d", &color[i], &cost[i]);
        sumn[color[i]]++;
        if(cost[i] <= p)
        {
            for(int j = 0; j < k; ++j)
            {
                sum_illegal += c(sum_temp[j]);
                sum_temp[j] = 0;
            }
        }
        else
        {
            sum_temp[color[i]]++;
        }
    }
    for(int j = 0; j < k; ++j)
        sum_illegal += c(sum_temp[j]);

    for(int j = 0; j < k; ++j)
    {
        sum_total += c(sumn[j]);
    }
    printf("%d
", sum_total - sum_illegal);
    return 0;
}