QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#194696#4931. Comic BingebruhWA 12ms160860kbC++203.8kb2023-09-30 21:46:472023-09-30 21:46:49

Judging History

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

  • [2023-09-30 21:46:49]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:160860kb
  • [2023-09-30 21:46:47]
  • 提交

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 = 2e4 + 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];   
    if (n == 1) {
        cout << a[1] + b[1];
        return; 
    }

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

    f[1][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 - 1];
                
            if (i > 2 && 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 - 2]);

            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: 8ms
memory: 160600kb

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: 12ms
memory: 160860kb

input:

2
2 1
1 1

output:

4

result:

ok single line: '4'

Test #3:

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

input:

1
1
1

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Wrong Answer
time: 7ms
memory: 160840kb

input:

161
146 662 336 441 626 77 362 697 911 248 879 40 435 60 518 62 475 908 185 740 435 899 188 673 716 529 524 305 321 998 4 363 598 471 650 379 6 980 971 175 664 328 294 681 201 64 926 608 310 478 404 284 634 239 891 515 433 368 929 457 593 338 432 971 593 134 355 97 658 344 653 592 822 660 403 398 38...

output:

80588

result:

wrong answer 1st lines differ - expected: '80587', found: '80588'