Contest Duration: - (local time) (100 minutes) Back to Home

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 2019-11-16 21:59:26+0900 E - All-you-can-eat NaomiatLibrary C++14 (GCC 5.4.1) 500 2605 Byte AC 204 ms 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