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

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 2019-11-16 21:50:14+0900 E - All-you-can-eat NaomiatLibrary C++14 (GCC 5.4.1) 0 2069 Byte TLE 2104 ms 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