QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#62275#2544. Flatland CurrencyhinataWA 189ms9360kbC++142.5kb2022-11-17 18:54:422022-11-17 18:54:43

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 18:54:43]
  • Judged
  • Verdict: WA
  • Time: 189ms
  • Memory: 9360kb
  • [2022-11-17 18:54:42]
  • 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, id; } C[N];
vector<NODE> v[5];
bool operator < (NODE x, NODE y){
    return x.x < y.x;
}
int sta[N];

void dfs(int x, int now, int cot){
    if(cot > m) return;
    if(x > 4){
        int top = 0;
        for(int i = 1; i <= n; ++i){
            if(!vis[C[i].id]){
                sta[++top] = C[i].x;
            }
        }
        int rest = m - cot;
        for(int i = 1; i <= top; ++i){
            if(rest > sta[i]){
                rest -= sta[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;
        if(val[i]) C[i] = (NODE) {12 / val[i] * cost[i], i};
    }
    sort(C + 1, C + 1 + n);
    for(int i = 1; i <= 4; ++i){
        v[i].push_back((NODE){0 ,0});
    }
    for(int i = 1; i <= n; ++i){
        if(val[i]){
            v[val[i]].push_back((NODE){cost[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: 3ms
memory: 5672kb

input:

5 57
9 14 31 18 27

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 0ms
memory: 5556kb

input:

4 50
11 11 11 11

output:

12

result:

ok answer is '12'

Test #3:

score: -100
Wrong Answer
time: 189ms
memory: 9360kb

input:

100000 89648823509660
921733427 402270498 51157221 585477094 435728758 913951087 580580944 557082810 585086423 837912728 799129405 867009344 751591136 714946046 464999915 256043168 416678301 183246216 569365122 479031618 435168577 31068363 903791719 497652990 960987871 223120213 395437892 112869678 ...

output:

893984

result:

wrong answer expected '200414', found '893984'