2014-01-21

■ SRM 605 23:21

Easy

貪欲。頭が悪いのでresubmitして-40ptsとかする。

//Bokan ga bokka--nn!! 
//Daily Lunch Special Tanoshii !! 
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
using namespace std; 
typedef pair<int,int> P; 
typedef pair<int,P> P1; 
typedef pair P2; 
typedef long long ll; 
#define pu push 
#define pb push_back 
#define mp make_pair 
#define eps 1e-7 
#define INF 2000000000 
#define f first 
#define s second 
#define rep(i,x) for(int i=0;i
class AlienAndHamburgers 
{ 
  public: 
  int getNumber(vector <int> type, vector <int> taste) 
  { 
    int n=type.size(); 
    int maxv[105]={}; 
    bool used[105]={}; 
    for(int i=0;iif(taste[i]>=0) 
      { 
        maxv[type[i]]+=taste[i]; 
        used[type[i]]=true; 
      } 
    } 
    for(int i=0;iif(!used[type[i]]) 
      { 
        if(maxv[type[i]]==0) 
        { 
          maxv[type[i]]=taste[i]; 
        } 
        else 
        { 
          maxv[type[i]]=max(maxv[type[i]],taste[i]); 
        } 
      } 
    } 
    for(int i=0;itrue; 
    } 
    vector<int>val; 
    int ret=0; 
    for(int i=0;i<105;i++) 
    { 
      if(used[i]) val.pb(maxv[i]); 
    } 
    sort(val.begin(),val.end(),greater<int>()); 
    int cur=0; 
    for(int i=0;i1)); 
    } 
    return ret; 
  } 
};

Med

ぜんぜん自明じゃなかったので点数が終わってます。

あとDP配列の初期化で詰まってて初心者が極まってました。

//Bokan ga bokka--nn!! 
//Daily Lunch Special Tanoshii !! 
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
using namespace std; 
typedef pair<int,int> P; 
typedef pair<int,P> P1; 
typedef pair P2; 
typedef long long ll; 
#define pu push 
#define pb push_back 
#define mp make_pair 
#define eps 1e-7 
#define INF 2000000000 
#define f first 
#define s second 
#define rep(i,x) for(int i=0;i
#define mod 1000000007 
ll dp[51][51][1024]={}; 
ll dpc[101][101]={}; 
class AlienAndSetDiv1 
{ 
  public: 
   
long long modpow(long long x,long long n) 
{ 
  long long res=1; 
  while(n>0) 
  { 
    if(n&1) res=res*x%mod; 
    x=x*x%mod; 
    n>>=1; 
  } 
  return res; 
} 
  int getNumber(int N, int K) 
  { 
    if(K>N) return 0; 
    if(K==1) 
    { 
      ll ret=1LL; 
      for(int i=2*N;i>=N+1;i--) 
      { 
        ret=(ret*i)%mod; 
      } 
      for(int i=1;i<=N;i++) 
      { 
        ret=(ret*modpow(1LL*i,1LL*mod-2))%mod; 
      } 
      return ret; 
    } 
    //0 is A 1 is B 
    dp[K-1][0][0]=1LL; 
    dp[0][K-1][(1<<(K-1))-1]=1LL; 
    //[\u37197][\u12427]DP 
    for(int i=K-1;i<2*N;i++) 
    { 
      for(int j=0;j<=N;j++) 
      { 
        if(i-j<0 || i-j>N) continue; 
        for(int k=0;k<(1<<(K-1));k++) 
        { 
          int v=__builtin_popcount(k); 
          if(j!=N) 
          { 
            if(j>=i-j || i-j-v>=j+1) 
            { 
              dp[j+1][i-j][k/2]=(dp[j+1][i-j][k/2]+dp[j][i-j][k])%mod; 
            } 
          } 
          if(i-j!=N) 
          { 
            if(j<=i-j || j-K+1+v>=i-j+1) 
            { 
              dp[j][i-j+1][(k/2)+(1<<(K-2))]=(dp[j][i-j+1][(k/2)+(1<<(K-2))]+dp[j][i-j][k])%mod; 
            } 
          } 
        } 
      } 
    } 
    ll res=0LL; 
    for(int i=0;i<(1<<(K-1));i++) 
    { 
      res=(res+dp[N][N][i])%mod; 
    } 
    return res; 
  } 
};

Challenge 落とせない人生

systest 通る人生

Rating 1770->1866(+96)

はやく2000代にしたいけどMedが難しすぎたりフローだったりすると終わるのでむずかしい

ツイートする