Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-21

PKU 3539 -- Elevator

| 18:10 | PKU 3539 -- Elevator - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3539 -- Elevator - Wrong Answer -- japlj PKU 3539 -- Elevator - Wrong Answer -- japlj のブックマークコメント

lo[x] := cで割った余りが x であるような階のうち、到達可能な最も低い階

をまずpriority queueとかで適当に計算すると、lo[x]+k*c (k >= 0) なる階にはすべて到達できるので 0 <= lo[x]+k*c < h なる k の数を全ての x について足せばよい。

TLEが厳しめっぽくて、 c の代わりに min{a,b,c} を使わないと通らなかった。


#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;

typedef long long ll;

int main()
{
  ll h, lo[100000];
  int a, b, c;
  scanf("%lld%d%d%d", &h, &a, &b, &c);
  if(c>b) swap(b,c); if(c>a) swap(a,c);
  for(int i=0; i<c; ++i) lo[i] = 1ll<<60;
  priority_queue<ll> Q;
  for(Q.push(0), lo[0]=0; !Q.empty(); ) {
    ll p = Q.top(); Q.pop();
    if(lo[(p+a)%c]>p+a) Q.push(p+a), lo[(p+a)%c]=p+a;
    if(lo[(p+b)%c]>p+b) Q.push(p+b), lo[(p+b)%c]=p+b;
  }
  ll sol = 0;
  for(int i=0; i<c; ++i) {
    if(lo[i] >= h) continue;
    ll hi = h-h%c+i;
    if(hi < h) hi += c;
    sol += (hi-lo[i])/c;
  }
  printf("%lld\n", sol);
  return 0;
}
 |