Submission #2241190


Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;

struct yakuhin {
  int a;
  int b;
  int c;
};

class Less{
public:
  bool operator()(const struct yakuhin& left, const struct yakuhin& right){
    return (left.a==right.a)?(left.b<right.b):(left.a<right.a);
  }
};

struct yakuhin zenhan[1048576];
struct yakuhin kouhan[1048576];

int main(){
  int n,Ma,Mb;
  cin >> n >> Ma >> Mb;
  struct yakuhin y[40];
  if(Ma>=Mb){
    for(int i=0;i<n;i++){
      cin >> y[i].a >> y[i].b >> y[i].c;
    }
  }else{
    for(int i=0;i<n;i++){
      cin >> y[i].b >> y[i].a >> y[i].c;
    }
  }
  for(int i=0;i<(1<<((n+1)/2));i++){
    zenhan[i].a = zenhan[i].b = zenhan[i].c = 0;
    for(int j=0;j<(n+1)/2;j++){
      if(i&(1<<j)){
        zenhan[i].a += y[j].a;
        zenhan[i].b += y[j].b;
        zenhan[i].c += y[j].c;
      }
    }
  }
  for(int i=0;i<(1<<(n/2));i++){
    kouhan[i].a = kouhan[i].b = kouhan[i].c = 0;
    for(int j=0;j<n/2;j++){
      if(i&(1<<j)){
        zenhan[i].a += y[j+(n+1)/2].a;
        zenhan[i].b += y[j+(n+1)/2].b;
        zenhan[i].c += y[j+(n+1)/2].c;
      }
    }
  }

  sort(zenhan,zenhan+(1<<((n+1)/2)),Less());
  sort(kouhan,kouhan+(1<<(n/2)),Less());

  int ans=1000000000;
  int k;
  for(int i=1;i<=10*n/Ma;i++){
    k=(1<<(n/2))-1;
    for(int j=0;j<(1<<((n+1)/2));j++){
      if(zenhan[j].a>Ma*i) break;
      while(zenhan[j].a+kouhan[k].a>Ma*i){
        k--;
      }
      if(zenhan[j].a+kouhan[k].a==Ma*i){
        while(zenhan[j].b+kouhan[k].b>Mb*i){
          k--;
          if(zenhan[j].a+kouhan[k].a!=Ma*i) break;
        }
        if(zenhan[j].b+kouhan[k].b==Mb*i){
          ans=((zenhan[j].c+kouhan[k].c<ans)?(zenhan[j].c+kouhan[k].c):ans);
        }
      }
    }
  }

  if(ans==1000000000) cout << -1 << endl;
  else cout << ans << endl;


  return 0;
}

Submission Info

Submission Time
Task D - Mixing Experiment
User yamunaku
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1894 Byte
Status WA
Exec Time 909 ms
Memory 24832 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 2
AC × 6
WA × 14
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All 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
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 2304 KB
sample_02.txt AC 2 ms 2304 KB
subtask_1_01.txt AC 2 ms 2304 KB
subtask_1_02.txt AC 2 ms 2304 KB
subtask_1_03.txt AC 2 ms 2304 KB
subtask_1_04.txt AC 2 ms 2304 KB
subtask_1_05.txt WA 2 ms 2304 KB
subtask_1_06.txt WA 2 ms 2304 KB
subtask_1_07.txt WA 2 ms 2304 KB
subtask_1_08.txt WA 3 ms 2304 KB
subtask_1_09.txt WA 8 ms 2432 KB
subtask_1_10.txt WA 43 ms 3072 KB
subtask_1_11.txt WA 169 ms 16640 KB
subtask_1_12.txt WA 909 ms 24832 KB
subtask_1_13.txt WA 446 ms 24832 KB
subtask_1_14.txt WA 340 ms 24832 KB
subtask_1_15.txt WA 314 ms 24832 KB
subtask_1_16.txt WA 375 ms 24832 KB
subtask_1_17.txt WA 323 ms 24832 KB
subtask_1_18.txt WA 337 ms 24832 KB