QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#62278 | #2544. Flatland Currency | hinata | WA | 3ms | 7616kb | C++14 | 2.9kb | 2022-11-17 19:10:14 | 2022-11-17 19:10:19 |
Judging History
answer
#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <ctime>
#include <cstdlib>
#include <set>
#include <cassert>
#include <string>
#include <map>
#include <unordered_map>
#include <random>
#include <string>
#include <vector>
using namespace std;
#define ll long long
#define llu unsigned long long
#define mem(a, b) memset(a, b, sizeof(a))
#define el printf("\n")
#define pii pair<int, int>
#define af assert(0)
#define _(x) cout<<#x<<" = "<<x<<"\n"
#define __(x, y) cout<<#x<<" = "<<x<<", "<<#y<<" = "<<y<<"\n"
#define rep(i, l, r) for(int i = (l); i <= (r); ++i)
#define dep(i, l, r) for(int i = (l); i <= (r); ++i)
#define int long long
const int N = 1e5 + 10;
const int limit[] = {0, 12, 6, 4, 3};
int n;
int cost[N], val[N], m, tot, vis[N], ans;
struct NODE { int x, val, id; } C[N];
vector<NODE> v[5];
bool operator < (NODE x, NODE y){
return x.x < y.x;
}
int sta[5][N], pos[5], s[N], s_top;
void dfs(int x, int now, int cot){
if(cot > m) return;
if(x > 4){
for(int i = 1; i <= 4; ++i) pos[i] = 0;
for(int i = 1; i <= n; ++i){
if(!vis[C[i].id]){
sta[C[i].val][++pos[C[i].val]] = C[i].x;
}
}
for(int i = 1; i <= 4; ++i){
int j;
int t = pos[i]; pos[i] = 0;
for(j = 1; j <= pos[i] - 3; j += 4){
int now = 0;
for(int k = j; k <= j + 3; ++k){
now += sta[i][k];
}
s[++s_top] = now;
// sta[++pos[i]] = now;
}
}
sort(s + 1, s + 1 + s_top);
int rest = m - cot;
for(int i = 1; i <= s_top; ++i){
if(rest > s[i]){
rest -= s[i];
now += 12;
}
else{
break;
}
}
ans = max(ans, now);
return;
}
int maxn = min((ll) v[x].size() - 1, limit[x] - 1);
for(int i = 0; i <= maxn; ++i){
vis[v[x][i].id] = 1;
dfs(x + 1, now + x * i, cot + v[x][i].x);
vis[v[x][i].id] = 0;
}
}
signed main(){
// freopen("1.in", "r", stdin);
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;
}
sort(C + 1, C + 1 + n);
for(int i = 1; i <= 4; ++i){
v[i].push_back((NODE){0 ,0 ,0});
}
for(int i = 1; i <= n; ++i){
if(val[i]){
v[val[i]].push_back((NODE){cost[i], val[i], 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].x = v[i][j - 1].x + v[i][j].x;
}
}
dfs(1, 0, 0);
printf("%lld\n", ans + tot);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7588kb
input:
5 57 9 14 31 18 27
output:
8
result:
ok answer is '8'
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 7616kb
input:
4 50 11 11 11 11
output:
8
result:
wrong answer expected '12', found '8'