2013年6月29日 星期六

NOIP2011 Day1.2.选择客栈 (ZJ a300)

// http://zerojudge.tw/ShowProblem?problemid=a300
#include<iostream>
#include<cstdio>
using namespace std;
int cnt[50][200001]; int num[200001];
int main()
{
    int n, k, p; scanf("%d %d %d", &n, &k, &p);
    for( int i = 0; i < k; i++){ cnt[i][0] = 0; }
    for( int i = 1; i <= n; i++)
    {
        for(int j = 0; j < k; j++){ cnt[j][i] = cnt[j][i-1]; }
        int t; scanf("%d %d", &t, &num[i]);
        cnt[t][i]++;
    }
    int ans = 0;
    for( int i = 1; i <= n; i++)
    {
        if( num[i] <= p )
        {
            int o = i+1;
            for(;o<=n;o++)
                if(num[o]<=p){break;}
            for(int j = 0; j < k; j++)
            {
             
                    ans += cnt[j][i] * ( cnt[j][o-1] - cnt[j][i-1] );
                    ans -= cnt[j][i]-cnt[j][i-1] ;
             }
     
        }
    }
    printf("%d\n", ans);
}

沒有留言:

張貼留言