Hatena::Grouptopcoder

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

 | 

2011-01-22

TKC03 -- Budget

19:46 | TKC03 -- Budget - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - TKC03 -- Budget - Wrong Answer -- japlj TKC03 -- Budget - Wrong Answer -- japlj のブックマークコメント

http://twitter.com/#!/tozangezan/status/28670225087995904

ここで問題が公開されていたので。

1~4はやるだけで、5(Budget)はOutput Onlyだけどやるだけだった。

掲載するソースは O(min{C} K log min{C} K) で、一番大きいケースでも2秒ぐらいで最適解を出す。


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

using namespace std;

int C[100000], cnt[100000] = {0};
int lo[1000000], prev[1000000], use[1000000];

int main()
{
  int K, N;
  scanf("%d%d", &K, &N);
  for(int i=0; i<K; ++i) scanf("%d", &C[i]);
  priority_queue<int> Q;
  int x = min_element(C, C+K) - C;
  for(int i=0; i<C[x]; ++i) lo[i] = N+1;
  for(Q.push(0), lo[0]=0; !Q.empty(); ) {
    int v = -Q.top(); Q.pop();
    for(int i=0; i<K; ++i) {
      int y = (v+C[i])%C[x];
      if(lo[y] > v+C[i]) {
	lo[y] = v+C[i];
	prev[y] = v%C[x];
	use[y] = i;
	Q.push(-(v+C[i]));
      }
    }
  }
  int sol = 0, mod;
  for(int i=0; i<C[x]; ++i) {
    if(lo[i] <= N) {
      int u = N - N%C[x] + i;
      while(u+C[x]<=N) u+=C[x];
      while(u>N) u-=C[x];
      if(u > sol) {
	sol = u;
	mod = i;
      }
    }
  }
  for(int p=mod; p!=0; ) {
    cnt[use[p]]++;
    sol -= C[use[p]];
    p = prev[p];
  }
  cnt[x] += sol/C[x];
  for(int i=0; i<K; ++i) printf("%d\n", cnt[i]);
  return 0;
}
 |