#45165: TLE求救


kaohoward (Orz)

學校 : 高雄市立高雄高級中學
編號 : 288265
來源 : [220.143.171.21]
最後登入時間 :
2025-01-22 11:35:02
a587. 祖靈好孝順 ˋˇˊ -- 祖靈的的大背包 | From: [114.39.6.138] | 發表日期 : 2025-01-19 14:59

求大神幫忙優化orz

#include<bits/stdc++.h>
using namespace std;
long long compute(long long a,long long b,long long x[],long long y[],long long sum1,long long sum2){
    if(a<0 || b<x[a]){
        return 0;
    }else if(b>=sum1){
        return sum2;
    }else{
        return max(compute(a-1,b-x[a],x,y,sum1-x[a],sum2-y[a])+y[a],compute(a-1,b,x,y,sum1-x[a],sum2-y[a]));
    }
}
int main()
{
    cin.sync_with_stdio(0);
    cout.sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long a,b,m;
    while(cin>>a){
            if(a==0){
                return 0;
            }
        long long x[a],y[a],sum1=0,sum2=0;
        for(int i=0;i<a;i++){
            cin>>x[i]>>y[i];
            sum1+=x[i];
            sum2+=y[i];
        }
        cin>>b;
        for(int i=a-1;i>=0;i--){
            for(int j=0;j<i;j++){
                if(x[j]<x[j+1]){
                    m=x[j];
                    x[j]=x[j+1];
                    x[j+1]=m;
                    m=y[j];
                    y[j]=y[j+1];
                    y[j+1]=m;
                }
            }
        }
        cout<<compute(a-1,b,x,y,sum1,sum2)<<"\n";
    }
    return 0;
}

 
ZeroJudge Forum