QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#62231 | #2544. Flatland Currency | hinata | WA | 4ms | 20468kb | C++14 | 3.6kb | 2022-11-17 17:29:07 | 2022-11-17 17:29:07 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int val[N], cost[N], n, m, tot;
int ans;
int f[100005];
void DP(){
for(int i = 1; i <= n ;++i){
for(int j = m; j >= cost[i]; --j){
f[j] = max(f[j], f[j - cost[i]] + val[i]);
}
}
printf("%lld\n", f[m] + tot);
}
namespace BF2{
const int MAXN = 1e6 + 10;
vector<int> v[5];
int f1[MAXN], f2[MAXN];
void dfs1(int x, int now, int cot){
if(cot > m) return;
if(x > 2){
f1[now] = min(f1[now], cot);
return;
}
dfs1(x + 1, now, cot);
int l = v[x].size();
for(int k = 0; k < l; ++k){
dfs1(x + 1, now + x * (k + 1), cot + v[x][k]);
}
}
int find(int v){
int l = 0, r = MAXN - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(f2[mid] <= v) l = mid;
else r = mid - 1;
}
return l;
}
void dfs2(int x, int now, int cot){
if(cot > m) return;
if(x > 4){
f2[now] = min(f2[now], cot);
return;
}
dfs2(x + 1, now, cot);
int l = v[x].size();
for(int k = 0; k < l; ++k){
dfs2(x + 1, now + x * (k + 1), cot + v[x][k]);
}
}
void solve(){
for(int i = 1; i <= n; ++i){
if(val[i] >= 0){
v[val[i]].push_back(cost[i]);
}
}
for(int i = 1; i <= 4; ++i){
sort(v[i].begin(), v[i].end());
for(int j = 1; j < v[i].size(); ++j){
v[i][j] += v[i][j - 1];
if(v[i][j] > 1e14 + 1) v[i][j] = 1e14 + 1;
}
}
memset(f1, 0x3f, sizeof(f1));
for(int x = 0; x < v[1].size(); ++x){
if(v[1][x] > m) continue;
for(int y = 0; y < v[2].size(); ++y){
int cot = v[1][x] + v[2][y], val = x+1 + 2 * (y+1);
if(cot > m) continue;
f1[val] = min(f1[val], cot);
}
}
memset(f2, 0x3f, sizeof(f2));
for(int x = 0; x < v[3].size(); ++x){
if(v[3][x] > m) continue;
for(int y = 0; y < v[4].size(); ++y){
int cot = v[3][x] + v[4][y], val = 3*(x+1) + 4*(y+1);
if(cot > m) continue;
f2[val] = min(f2[val], cot);
}
}
for(int i = MAXN - 2; i >= 0; --i){
f1[i] = min(f1[i], f1[i + 1]);
}
f1[0] = 0;
for(int i = MAXN - 2; i >= 0; --i){
f2[i] = min(f2[i], f2[i + 1]);
}
f2[0] = 0;
for(int i = 0; i <= MAXN - 10; ++i){
if(m - f1[i] >= 0)
ans = max(ans, i + find(m - f1[i]));
}
// for(int i = 0; i <= )
printf("%lld\n", ans + tot);
}
}
signed main(){
// freopen("DD.in", "r", stdin);
// freopen("DD.out", "w", stdout);
scanf("%lld %lld", &n, &m);
tot = m % 5; m -= m % 5;
for(int i = 1; i <= n; ++i){
int x; scanf("%lld", &x);
cost[i] = x + (5 - x % 5) % 5;
val[i] = (5 - x % 5) % 5;
}
// for(int i = 1; i <= n; ++i) printf("%lld ", cost[i]); printf("\n");
// for(int i = 1; i <= n; ++i) printf("%lld ", val[i]); printf("\n");
// BF2::solve(); return 0;
// if(m <= 100000) DP();
BF2 :: solve();
return 0;
}
/*
5 57
9 14 31 18 27
4 50
11 11 11 11
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 20468kb
input:
5 57 9 14 31 18 27
output:
6
result:
wrong answer expected '8', found '6'