QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#728203#4931. Comic Bingepnlong2706WA 1ms3972kbC++173.2kb2024-11-09 14:45:522024-11-09 14:45:58

Judging History

This is the latest submission verdict.

  • [2024-11-09 14:45:58]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3972kb
  • [2024-11-09 14:45:52]
  • Submitted

answer

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll          long long
#define ull         unsigned long long
#define ld          long double
#define for_(n)     for(ll i=0; i<n; i++)
#define for__(a,b)  for(ll i=a; i<b; i++)
#define _for(i,a,b) for(ll i=a; i<b; i++)
#define mp          make_pair
#define fi          first
#define se          second
#define pb          push_back
#define pii         pair<int, int>
#define pll         pair<long long, long long>
#define el          "\n"
#define debug(x)    if(enable_debug) cerr << "[debug] " << #x << " : " << x << endl;
#define M_PI        3.14159265358979323846

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;

typedef tree<ll,null_type, less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const long long MOD=(ll)1e9+7;
const bool enable_debug = true;

template<class T, class P>
ostream& operator<<(ostream& os, const pair<T,P> &a) { os << "{" << a.first << ";" << a.second << "}"; return os; }
template<class T>
ostream& operator<<(ostream& os, const vector<T> &a) { ; for(auto it: a) os << it << " "; ; return os; }
template<class T>
ostream& operator<<(ostream& os, const deque<T> &a) { ; for(auto it: a) os << it << " "; ; return os; }
template<class T>
ostream& operator<<(ostream& os, const set<T> &a) { ; for(auto it: a) os << it << " "; ; return os; }
template<class T>
ostream& operator<<(ostream& os, const multiset<T> &a) { ; for(auto it: a) os << it << " "; ; return os; }

ll gcd(ll a, ll b) { return b==0? a : gcd(b,a%b); }
ll lcm(ll a, ll b) { return a/(gcd(a,b))*b; }

ll pow_mod(ll x, ll y, ll mod) { //mod<3.10^9
    ll ans=1;
    while(y>0) {
        if(y%2==1) ans=ans*x%mod;
        y=y>>1;
        x=x*x%mod;
    }
    return ans%mod;
}

void solve(int ith) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);

    for_(n) cin >> a[i];
    for_(n) cin >> b[i];

    vector<vector<int>> dp(n*11, vector<int> (n+1, -1));

    int ans = 1e9;
    dp[b[0]][0] = b[0] + a[0];
    for(int i=b[0]+1; i<n*11; i++) {
        for(int j=1; j<n; j++) {
            if(i-b[j] > 0 && dp[i-b[j]][j-1]!=-1) dp[i][j] = max(dp[i-b[j]][j-1], i) + a[j]; 
            if(j>=2) {
                if(i-b[j] > 0 && dp[i-b[j]][j-2]!=-1) dp[i][j] = max(dp[i-b[j]][j-2] + a[j-1], i) + a[j];
            }
            //cout << i << " " << j << " " << dp[i][j] << el;
        }
        if(dp[i][n-1]!=-1) ans = min(ans, dp[i][n-1]);
    }

    cout << ans << el;
}

// PLEASE DO CHECK THE CASE THAT YOU CHANGE THE ORIGINAL VALUE OF SOME VAR AND THEN TRY TO USE THE OLD VALUE OF THAT VAR FOR
// ANOTHER EVALUATION IN THE SAME SCOPE

int main() {
    clock_t begin=clock();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    #ifndef ONLINE_JUDGE
    freopen("INP.inp","r",stdin);
    freopen("OUT.out", "w", stdout);
    #endif

    int t = 1;
    //cin >> t;
    for_(t)
        solve(i+1);
    cerr << "TIME : " << (double)(clock()-begin)/CLOCKS_PER_SEC << "s.";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3972kb

input:

6
3 1 1 1 1 2
1 5 3 3 7 4

output:

13

result:

ok single line: '13'

Test #2:

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

input:

2
2 1
1 1

output:

4

result:

ok single line: '4'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3864kb

input:

1
1
1

output:

1000000000

result:

wrong answer 1st lines differ - expected: '2', found: '1000000000'