Submission #8481503


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)*2];
      	initdp();
    }
    int mkitr(int x,int y,int n){
        return x*(C+1)+y+(C+1)*(N+1)*n;
    }
    void initdp(){
        rep(i,N+1){
            rep(j,C+1){
                rep(k,2){
                    dp[mkitr(i,j,k)]=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,0)]=dp[mkitr(i-1,j,0)];
                if(j>0)dp[mkitr(i,j,0)]=max(dp[mkitr(i,j,0)],dp[mkitr(i,j-1,0)]);
                int p=prods[i-1].second;int c=prods[i-1].first;
                if(j-c>=0)dp[mkitr(i,j,0)]=max(dp[mkitr(i,j,0)],dp[mkitr(i-1,j-c,0)]+p);
                //もう最後のを使ったもしくはちょうど使う
                dp[mkitr(i,j,1)]=dp[mkitr(i-1,j,1)];
                if(j>0)dp[mkitr(i,j,1)]=max(dp[mkitr(i,j,1)],dp[mkitr(i,j-1,1)]);
                //もう使ったのでそのまま
                if(j-c>=0)dp[mkitr(i,j,1)]=max(dp[mkitr(i,j,1)],dp[mkitr(i-1,j-c,1)]+p);
                //まだ使ってないので無料使う
                c=0;
                if(j-c>=0)dp[mkitr(i,j,1)]=max(dp[mkitr(i,j,1)],dp[mkitr(i-1,j-c,0)]+p);
            }
        }
        return dp[mkitr(N,C,1)];
    }
    void debug_printdp(){
        rep(i,N+1){
            rep(j,C+1){printf("%lld ",dp[mkitr(i,j,0)]);}
            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;
    Napsack_multino NP(T-1,N);
    rep(i,N){
        NP.push_prods(A[i],B[i]);
    }
    ans=NP.solve();
    printf("%lld\n",ans);
    return 0;
}

Submission Info

Submission Time
Task E - All-you-can-eat
User NaomiatLibrary
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2605 Byte
Status AC
Exec Time 204 ms
Memory 141056 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87: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:89: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 500 / 500
Status
AC × 4
AC × 31
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 8 ms 6400 KB
corner_02 AC 38 ms 30464 KB
corner_03 AC 49 ms 33664 KB
corner_04 AC 9 ms 6016 KB
corner_05 AC 10 ms 6272 KB
corner_06 AC 10 ms 6144 KB
corner_07 AC 49 ms 31616 KB
hand_01 AC 1 ms 256 KB
hand_02 AC 1 ms 256 KB
max_01 AC 186 ms 138496 KB
max_02 AC 181 ms 134528 KB
max_03 AC 161 ms 141056 KB
max_04 AC 161 ms 141056 KB
max_05 AC 201 ms 140928 KB
max_06 AC 204 ms 141056 KB
max_07 AC 202 ms 140928 KB
max_08 AC 204 ms 141056 KB
random_01 AC 29 ms 23040 KB
random_02 AC 15 ms 12160 KB
random_03 AC 66 ms 48896 KB
random_04 AC 15 ms 11776 KB
random_05 AC 27 ms 20864 KB
random_06 AC 85 ms 67584 KB
random_07 AC 86 ms 65664 KB
random_08 AC 16 ms 11776 KB
random_09 AC 68 ms 50560 KB
random_10 AC 70 ms 55424 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