QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#194571#4931. Comic BingebruhWA 4ms82088kbC++203.7kb2023-09-30 21:09:082023-09-30 21:09:10

Judging History

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

  • [2023-09-30 21:09:10]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:82088kb
  • [2023-09-30 21:09:08]
  • 提交

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>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef __int128 Int;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef pair<ll, ii> iii;
typedef unordered_map<ll, ll> unmap;

template<typename T> using pqmax = priority_queue<T>;
template<typename T> using pqmin = priority_queue<T, vector<T>,greater<T>>;
template<typename T> using oset = tree<T, null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define fi first
#define se second
#define sz size()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define lg(n) (ll)__lg(n)
#define btpc __builtin_popcount

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define FOR(i,a,b) for(ll i = a; i <= b; i ++)
#define REP(i,a,b) for(ll i = a; i < b; i ++)
#define FORD(i,a,b) for(ll i = a; i >= b; i --)
#define FORS(i,a,b,c) for(ll i = a; i <= b; i += c)
#define FORDS(i,a,b,c) for(ll i = a; i >= b; i -= c)
#define FORA(x,a) for(auto x: a)
#define FORAA(l,r,a) for(auto [l, r]: a)

#define EL cerr << endl;
#define DEBUGN(a) cerr << a << endl;
#define DEBUGA(a, n) FOR (i, 1, n) cerr << a[i] << " "; cerr << endl;
#define DEBUG_AOP(a, n) FOR (i, 1, n) cerr << a[i].fi << " " << a[i].se << endl;  
#define DEBUG_A2D(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cerr << a[i][j] << " "; cerr << endl;}
#define DEBUG cerr << "shut the fuck up please :3" << endl;

#define YES cout << "YES\n"; return;
#define NO cout << "NO\n"; return;
 
template<class X, class Y> bool mimi(X &x, const Y &y) {if(x>y){x=y;return 1;}return 0;}
template<class X, class Y> bool mama(X &x, const Y &y) {if(x<y){x=y;return 1;}return 0;}
istream &operator >> (istream &st, Int &a) {string s;a=0;st>>s;bool g=1;REP(i,0,s.sz){if(i==0&&s[i]=='-'){g = 0;continue;}a=a*10+s[i]-'0';}if(!g)a=-a;return st;}
ostream &operator << (ostream &st, const Int &a) {Int t=a;if(t==0){st<<0;return st;}if(t<0){st<<'-';t=-t;}string b;while(t!=0){b.pb((t%10+'0'));t/=10;}reverse(all(b));st<<b;return st;}

const ll nom = 2;
const ll base[] = {577, 677, 877, 977};
const ll mod[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277};
const ii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

const ll INF = 1e18;
const ll N = 1e3 + 5;
const ll T = 4*N - 3;
const ll M = 1e9 + 7;

const ll LIM = 1e4 + 5;
ll n;
ll a[N], b[N], f[N][LIM], s[N];

void solve(ll testID) {
    cin >> n;
    FOR (i, 1, n) {cin >> a[i]; s[i] = s[i - 1] + a[i];}
    FOR (i, 1, n) cin >> b[i];   

    REP (i, 0, N)
        REP (j, 0, LIM)
            f[i][j] = -INF;

    f[0][b[1]] = 0;
    FOR (i, 2, n) {
        REP (j, 0, LIM) {
            if (j - b[i] >= 0 && f[i - 1][j - b[i]] != -INF) 
                f[i][j] = f[i - 1][j - b[i]] + b[i];
                
            if (j - b[i] >= 0 && f[i - 2][j - b[i]] != -INF)
                f[i][j] = max(f[i][j], f[i - 2][j - b[i]] + b[i]);

            if (f[i][j] != -INF) {
                f[i][j] = min(f[i][j], s[i]);
                // cout << i << " " << j << " " << f[i][j] << endl;
            }
        }
    }

    ll res = INF;
    REP (j, 0, LIM)
        if (f[n][j] != -INF) {
            // cout << j << " " << f[n][j] << " " << j + s[n] - f[n][j] << endl;
            res = min(res, j + s[n] - f[n][j]);
        }

    cout << res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int test = 1;
    // cin >> test;
    FOR (i, 1, test) solve(i);
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 81992kb

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: 4ms
memory: 82088kb

input:

2
2 1
1 1

output:

4

result:

ok single line: '4'

Test #3:

score: -100
Wrong Answer
time: 4ms
memory: 81988kb

input:

1
1
1

output:

1000000000000000000

result:

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