QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#62278#2544. Flatland CurrencyhinataWA 3ms7616kbC++142.9kb2022-11-17 19:10:142022-11-17 19:10:19

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-17 19:10:19]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 7616kb
  • [2022-11-17 19:10:14]
  • Submitted

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;
}

详细

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'