AtCoder Beginner Contest 054

Submission #1128677

Source codeソースコード

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n,ma,mb;
  cin>>n>>ma>>mb;
  vi a(n),b(n),c(n);
  rep(i,n)
    cin>>a[i]>>b[i]>>c[i];

  map<pii,int> x;
  rep(i,1<<(n/2)){//前半を全列挙                                                                 
    int ta=0,tb=0,tc=0;
    rep(j,n/2)
      if((i&(1<<j))!=0){//iのj桁目が1のとき                                                      
        ta+=a[j];
        tb+=b[j];
        tc+=c[j];
      }
    if(x.count(pii(ta,tb)))//存在するとき                                                        
      x[pii(ta,tb)]=min(x[pii(ta,tb)],tc);
    else
      x[pii(ta,tb)]=tc;
  }

  map<pii,int> y;
  rep(i,1<<(n-n/2)){//後半を全列挙                                                               
    int ta=0,tb=0,tc=0;
    rep(j,n-n/2)
      if((i&(1<<j))!=0){//iのj桁目が1のとき                                                      
        ta+=a[j+n/2];
        tb+=b[j+n/2];
        tc+=c[j+n/2];
      }
    if(y.count(pii(ta,tb)))//存在するとき                                                        
      y[pii(ta,tb)]=min(y[pii(ta,tb)],tc);
    else
      y[pii(ta,tb)]=tc;
  }

  int ans=INF;
  for(map<pii,int>::iterator itr=x.begin();itr!=x.end();itr++){
    int ta=(*itr).first.first;
    int tb=(*itr).first.second;
    for(i=1;i*max(ma,mb)<405;i++)
      if(y.count(pii(i*ma-ta,i*mb-tb)))
        ans=min(ans,(*itr).second+y[pii(i*ma-ta,i*mb-tb)]);
  }
  if(ans<INF)
    cout<<ans<<endl;
  else
    cout<<-1<<endl;
}

Submission

Task問題 D - Mixing Experiment
User nameユーザ名 rika
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 2175 Byte
File nameファイル名
Exec time実行時間 610 ms
Memory usageメモリ使用量 896 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
All 400 / 400 sample_01.txt,sample_02.txt,subtask_1_01.txt,subtask_1_02.txt,subtask_1_03.txt,subtask_1_04.txt,subtask_1_05.txt,subtask_1_06.txt,subtask_1_07.txt,subtask_1_08.txt,subtask_1_09.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_16.txt,subtask_1_17.txt,subtask_1_18.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt AC 2 ms 256 KB
subtask_1_07.txt AC 3 ms 384 KB
subtask_1_08.txt AC 4 ms 384 KB
subtask_1_09.txt AC 14 ms 512 KB
subtask_1_10.txt AC 50 ms 512 KB
subtask_1_11.txt AC 238 ms 640 KB
subtask_1_12.txt AC 610 ms 896 KB
subtask_1_13.txt AC 491 ms 768 KB
subtask_1_14.txt AC 497 ms 768 KB
subtask_1_15.txt AC 484 ms 768 KB
subtask_1_16.txt AC 515 ms 896 KB
subtask_1_17.txt AC 512 ms 896 KB
subtask_1_18.txt AC 520 ms 768 KB