Submission #1107900


Source Code Expand

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define sort(v,n) sort(v,v+n);
#define vsort(v) sort(v.begin(),v.end());
#define vvsort(v) sort(v.begin(),v.end(),greater<int>());
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
typedef pair<int,int> p;
typedef pair<ll,ll> lp;
typedef priority_queue<int> pq;
typedef priority_queue<int,vector<int>,greater<int> > rpq;
bool is_uruu(int y) {
        return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}
const ll MOD=1e9+7;
const double PI=acos(-1.0);
//----------------------------------------------------------------------------------------------------------------------------------//
int n,Ma,Mb;
int a[50],b[50],c[50];
int dp[50][500][500];
int main(){
        cin>>n>>Ma>>Mb;
        for(int i=0; i<n; i++) {
                cin>>a[i]>>b[i]>>c[i];
        }
        for(int i=0; i<50; i++) {
                for(int j=0; j<500; j++) {
                        for(int k=0; k<500; k++) {
                                dp[i][j][k]=inf;
                        }
                }
        }
        dp[0][0][0]=0;
        for(int i=0; i<n; i++) {
                for(int j=0; j<500; j++) {
                        for(int k=0; k<500; k++) {
                                dp[i+1][j+a[i]][k+b[i]]=min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i]);
                                dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]);
                        }
                }
        }
        int mindp=inf;
        for(int i=1; i<500; i++) {
                for(int j=1; j<500; j++) {
                        int g=__gcd(i,j);
                        if(i/g==Ma && j/g==Mb) {
                                mindp=min(mindp,dp[n][i][j]);
                        }
                }
        }
        if(mindp==inf) {
                cout<< -1<<endl;
                return 0;
        }
        cout<<mindp<<endl;
}

Submission Info

Submission Time
Task D - Mixing Experiment
User aim_cpo
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2098 Byte
Status AC
Exec Time 86 ms
Memory 49024 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 18
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All 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 66 ms 49024 KB
sample_02.txt AC 65 ms 49024 KB
subtask_1_01.txt AC 68 ms 49024 KB
subtask_1_02.txt AC 65 ms 49024 KB
subtask_1_03.txt AC 68 ms 49024 KB
subtask_1_04.txt AC 70 ms 49024 KB
subtask_1_05.txt AC 72 ms 49024 KB
subtask_1_06.txt AC 74 ms 49024 KB
subtask_1_07.txt AC 76 ms 49024 KB
subtask_1_08.txt AC 77 ms 49024 KB
subtask_1_09.txt AC 79 ms 49024 KB
subtask_1_10.txt AC 82 ms 49024 KB
subtask_1_11.txt AC 84 ms 49024 KB
subtask_1_12.txt AC 85 ms 49024 KB
subtask_1_13.txt AC 85 ms 49024 KB
subtask_1_14.txt AC 85 ms 49024 KB
subtask_1_15.txt AC 85 ms 49024 KB
subtask_1_16.txt AC 86 ms 49024 KB
subtask_1_17.txt AC 86 ms 49024 KB
subtask_1_18.txt AC 85 ms 49024 KB