Submission #8479984


Source Code Expand

Copy
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back

struct Napsack_multino{
    int C;
    int N;
    pair<int,int> *prods;
    int *dp;
    int prod_count; 
    Napsack_multino(int c,int n){
      	C=c;N=n;
        prods = new pair<int,int>[N];
        prod_count=0;
        dp = new int[(C+2)*(N+2)];
      	initdp();
    }
    int mkitr(int x,int y){
        return x*(C+1)+y;
    }
    void initdp(){
        rep(i,N+1){
            rep(j,C+1){
                dp[mkitr(i,j)]=0;
            }
        }
    }
    void push_prods(int c,int p){
        prods[prod_count++]=mp(c,p);
    }
    int solve(){
        initdp();
        rep(i,N+1){
            if(i>0)rep(j,C+1){
                dp[mkitr(i,j)]=dp[mkitr(i-1,j)];
                if(j>0)dp[mkitr(i,j)]=max(dp[mkitr(i,j)],dp[mkitr(i,j-1)]);
                int p=prods[i-1].second;int c=prods[i-1].first;
                if(j-c>=0)dp[mkitr(i,j)]=max(dp[mkitr(i,j)],dp[mkitr(i-1,j-c)]+p);
            }
        }
        return dp[mkitr(N,C)];
    }
    void debug_printdp(){
        rep(i,N+1){
            rep(j,C+1){printf("%lld ",dp[mkitr(i,j)]);}
            printf("\n");
        }
    }
    void free_(){
        delete[] prods;
        delete[] dp;
    }
    
};


int MOD=1000000007;
int N,T;
int A[3005],B[3005];
char S[1000];
signed main(){
    scanf("%lld %lld",&N,&T);
    rep(i,N){
        scanf("%lld %lld",&A[i],&B[i]);
    }
    //最後に食べるものを選んでナップサック
    int ans=0;
    rep(i,N){
        Napsack_multino NP(T-1,N);
        rep(j,N){
            if(i!=j)NP.push_prods(A[j],B[j]);
        }
        ans=max(ans,NP.solve()+B[i]);
        NP.free_();
    }
    printf("%lld",ans);
    return 0;
}

Submission Info

Submission Time
Task E - All-you-can-eat
User NaomiatLibrary
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2069 Byte
Status TLE
Exec Time 2104 ms
Memory 70720 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:76:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&N,&T);
                             ^
./Main.cpp:78:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld",&A[i],&B[i]);
                                       ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 4
AC × 11
TLE × 20
Set Name Test Cases
Sample sample_01, sample_02, sample_03, sample_04
All corner_01, corner_02, corner_03, corner_04, corner_05, corner_06, corner_07, hand_01, hand_02, max_01, max_02, max_03, max_04, max_05, max_06, max_07, max_08, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
corner_01 AC 1675 ms 3340 KB
corner_02 TLE 2103 ms 15380 KB
corner_03 TLE 2103 ms 16896 KB
corner_04 AC 285 ms 3148 KB
corner_05 AC 315 ms 3252 KB
corner_06 AC 308 ms 3200 KB
corner_07 TLE 2103 ms 16000 KB
hand_01 AC 1 ms 256 KB
hand_02 AC 1 ms 256 KB
max_01 TLE 2104 ms 69440 KB
max_02 TLE 2104 ms 67476 KB
max_03 TLE 2104 ms 70720 KB
max_04 TLE 2104 ms 70720 KB
max_05 TLE 2104 ms 70672 KB
max_06 TLE 2103 ms 70720 KB
max_07 TLE 2104 ms 70680 KB
max_08 TLE 2104 ms 70720 KB
random_01 TLE 2103 ms 11704 KB
random_02 TLE 2103 ms 6240 KB
random_03 TLE 2103 ms 24732 KB
random_04 TLE 2103 ms 6016 KB
random_05 TLE 2103 ms 10568 KB
random_06 TLE 2103 ms 33984 KB
random_07 TLE 2104 ms 33024 KB
random_08 AC 985 ms 6124 KB
random_09 TLE 2104 ms 25552 KB
random_10 TLE 2104 ms 27904 KB
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 AC 1 ms 256 KB
sample_04 AC 1 ms 256 KB