Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2263-294be851
この記事にトラックバックする(FC2ブログユーザー)

Round #115 C問題 - Geometry Horse (この記事を編集する[管理者用])

Source

RazMERiq 2012 C問題
Codeforces Round #115 C問題
Problem description

問題概要

コンボのあるシューティングゲーム的な何か.
N種類 (100以下) だけ敵の種類がある.
種類iはK[i]匹 (10^9以下) おり,倒した時にもらえる基本スコアはC[i] (1000以下) である.
好きな順番で倒して良い.
T個 (100以下) の整数P[i] (10^12以下) が与えられる.P[i] < P[i+1].
敵を既にP[i]匹以上倒している (かつP[i+1]匹倒していない) なら,敵を倒した時にもらえるスコアがi+1倍になる.
最終的に獲得可能な最大スコアを求める問題.

解法

Greedy.
だんだん倍率が高くなるので,スコアの小さい敵から倒していけば良い.
1匹ずつ処理するのではなく,同じ種類の敵がいなくなるか,倍率が変わるまで一気に処理する.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}

int main(){
  int i,j,l,m,n;
  int k[2000], c[2000];
  ll p[110], t, f, num, go;
  ll res;

  scanf("%d",&n);
  rep(i,n) scanf("%d%d",k+i,c+i);
  scanf("%I64d",&t);
  rep(i,t) scanf("%I64d",p+i);
  p[t] = 1000000000000000000LL;

  intIntSort(c,k,n);

  res = 0;
  num = 0;
  f = 0;

  m = 0;
  while(m < n){
    go = p[f] - num;
    if(go > k[m]) go = k[m];

    res += go * c[m] * (f+1);
    k[m] -= go;
    num += go;

    if(k[m] <= 0) m++;
    while(num == p[f]) f++;
  }

  printf("%I64d\n",res);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2263-294be851
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。