QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#62231#2544. Flatland CurrencyhinataWA 4ms20468kbC++143.6kb2022-11-17 17:29:072022-11-17 17:29:07

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-17 17:29:07]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:20468kb
  • [2022-11-17 17:29:07]
  • 提交

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'