Submission #3051514


Source Code Expand

#include <bits/stdc++.h>
#include <string.h>
using namespace std;

///////////////////////////////////////////
//const long long int INF = 1000000000000000000LL;
const long long int INF = 1000000;
using ll = long long int;
using vi = vector<int>;
using Vi = vector<long long int>;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
auto max(auto x,auto y){if(x>y){return x;}else{return y;}}
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return 1; } return 0; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return 1; } return 0; }
template<class T>T sqar(T x){ return x*x; }
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(    v[0])>()) //降順でVをソート
///////////////////////////////////////////

ll n,ma,mb;
vi a,b,c;
ll dp[50][401][401]; //dp[i][j][k] := i番目まででaがj,bがkとなる最小の値段
/*
 * dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a[i]][
 */
void cal(int num,int x,int y){
    // cout<<"num,x,y : "<<num<<" , "<<x<<" , "<<y<<" , "<<dp[num][x][y]<<endl;
    if(num>=n) {

    }else if(dp[num][x][y]==INF){

    }else{
        chmin(dp[num+1][x+a[num]][y+b[num]],dp[num][x][y]+c[num]);
        chmin(dp[num+1][x][y],dp[num][x][y]);
        cal(num+1,x,y);
        cal(num+1,x+a[num],y+b[num]);
    }
}

int main(){
    cin>>n>>ma>>mb;
    int aa,bb,cc;
    rep(i,50)rep(j,401)rep(k,401)dp[i][j][k]=INF;
    dp[0][0][0]=0;
    //ll key = 0;
    rep(i,n){
        cin>>aa>>bb>>cc;
        a.pb(aa);
        //key+=aa;
        b.pb(bb);
        c.pb(cc);
    }
    cal(0,0,0);
    ll ans = INF;
    for(int i =1;i<50;i++){
        if(ma*i>490 || mb*i>490){
            break;
        }else{
            chmin(ans,dp[n][ma*i][mb*i]);
        }
    }
    if(ans==INF){
        cout<<-1<<endl;
    }else{
        cout<<ans<<endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - Mixing Experiment
User emile11235
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1978 Byte
Status TLE
Exec Time 2104 ms
Memory 63104 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 2
AC × 11
TLE × 9
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 19 ms 63104 KB
sample_02.txt AC 19 ms 63104 KB
subtask_1_01.txt AC 19 ms 63104 KB
subtask_1_02.txt AC 19 ms 63104 KB
subtask_1_03.txt AC 19 ms 63104 KB
subtask_1_04.txt AC 18 ms 63104 KB
subtask_1_05.txt AC 19 ms 63104 KB
subtask_1_06.txt AC 21 ms 63104 KB
subtask_1_07.txt AC 35 ms 63104 KB
subtask_1_08.txt AC 82 ms 63104 KB
subtask_1_09.txt AC 1987 ms 63104 KB
subtask_1_10.txt TLE 2104 ms 63104 KB
subtask_1_11.txt TLE 2104 ms 63104 KB
subtask_1_12.txt TLE 2104 ms 63104 KB
subtask_1_13.txt TLE 2104 ms 63104 KB
subtask_1_14.txt TLE 2104 ms 63104 KB
subtask_1_15.txt TLE 2104 ms 63104 KB
subtask_1_16.txt TLE 2104 ms 63104 KB
subtask_1_17.txt TLE 2104 ms 63104 KB
subtask_1_18.txt TLE 2104 ms 63104 KB