Submission #1304722
Source Code Expand
#include <cstdio>
#include <vector>
struct state {
int aw;
int av;
state(int aw=0, int av=0): aw(aw), av(av) {}
};
int n, w, c;
std::vector<state> is[50];
std::vector<state> tmp;
std::vector<state> dp[51][2];
void merge(const std::vector<state> &s, const std::vector<state> &t, std::vector<state> &u){
auto i = s.cbegin();
auto j = t.cbegin();
for(; i != s.cend() && j != t.cend();){
if(i->aw <= j->aw && i->av >= j->av) ++j;
else if(i->aw >= j->aw && i->av <= j->av) ++i;
else if(i->aw < j->aw) u.push_back(*i++);
else u.push_back(*j++);
}
while(i != s.cend()) u.push_back(*i++);
while(j != t.cend()) u.push_back(*j++);
}
void mergei(const std::vector<state> &s, const state &k, std::vector<state> &u){
auto i = s.cbegin();
auto j = s.cbegin();
for(; i != s.cend() && j != s.cend() && j->aw + k.aw <= w;){
if(i->aw <= j->aw + k.aw && i->av >= j->av + k.av) ++j;
else if(i->aw >= j->aw + k.aw && i->av <= j->av + k.av) ++i;
else if(i->aw < j->aw + k.aw) u.push_back(*i++);
else {u.emplace_back(state(j->aw + k.aw, j->av + k.av)); ++j;}
}
while(i != s.cend()) u.push_back(*i++);
while(j != s.cend() && j->aw + k.aw <= w){
u.emplace_back(state(j->aw + k.aw, j->av + k.av));
++j;
}
}
int main(){
scanf("%d%d%d", &n, &w, &c);
for(int i=0;i<n;i++){
int ww, vv, cc;
scanf("%d%d%d",&ww,&vv,&cc);
is[cc-1].emplace_back(state(ww, vv));
}
for(int i=0;i<=50;i++){
dp[i][0].emplace_back(state(0, 0));
dp[i][1].emplace_back(state(0, 0));
}
for(int i=0;i<50;i++){
if(is[i].empty()) continue;
for(int k = 1; k <= c; k++){
merge(dp[k][1], dp[k][0], tmp);
dp[k][0].swap(tmp);
tmp.resize(0);
dp[k][1].resize(0);
mergei(dp[k-1][0], is[i][0], dp[k][1]);
}
for(auto j = is[i].cbegin()+1; j != is[i].cend(); ++j){
// for(int k = 1; k <= c; k++){
for(int k = c-(50-i); k <= c; k++){
mergei(dp[k][1], *j, tmp);
dp[k][1].swap(tmp);
tmp.resize(0);
}
}
}
printf("%d\n", std::max(dp[c][0].back().av, dp[c][1].back().av));
return 0;
}
Submission Info
Submission Time |
|
Task |
H - ナップザック |
User |
ryuhei |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2224 Byte |
Status |
RE |
Exec Time |
97 ms |
Memory |
256 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:51:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &w, &c);
^
./Main.cpp:54:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&ww,&vv,&cc);
^
Judge Result
Set Name |
All |
Score / Max Score |
0 / 5 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 03, 04, 05, 08, 09, 10, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
RE |
96 ms |
256 KB |
01 |
RE |
96 ms |
256 KB |
02 |
RE |
96 ms |
256 KB |
03 |
RE |
96 ms |
256 KB |
04 |
RE |
96 ms |
256 KB |
05 |
RE |
96 ms |
256 KB |
08 |
RE |
96 ms |
256 KB |
09 |
RE |
95 ms |
256 KB |
10 |
RE |
96 ms |
256 KB |
90 |
AC |
1 ms |
256 KB |
91 |
RE |
97 ms |
256 KB |