Submission #28053673

Source Code Expand

#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define rep2(i,k,n) for (ll i = (k); i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
// using P = pair<ll,ll>;

const ll INF = (ll)1e18;
// const int INF = (int)1e9+7;
template<typename T>
void chmin(T &a, T b) { a = min(a, b); }
template<typename T>
void chmax(T &a, T b) { a = max(a, b); }

ll get(ll S, ll j) {
    ll ans = 0;
    rep(i,j) {
        if ((~S)>>i & 1) ans++;
    }
    return ans;
}

void solve() {
    ll N, X, Y;
    cin >> N >> X >> Y;
    vector<ll> A(N+1), B(N+1);
    rep(i,N) cin >> A[i+1];
    rep(i,N) cin >> B[i+1];

    vector<vector<ll>> dp(N+1, vector<ll>(1<<N, INF));
    dp[0][0] = 0;
    rep2(i,1,N+1) {
        rep(S,1<<N) {
            rep(j,N) {
                if ((S & (1<<j)) > 0) continue;
                chmin(dp[i][S|(1<<j)], dp[i-1][S] + get(S, j) * Y + abs(A[j+1] - B[i])*X);
            }
        }
    }

    cout << dp[N][(1<<N)-1] << endl;
}

int main() {
    solve();
    return 0;
}

Submission Info

Submission Time
Task F - Simple Operations on Sequence
User goropikari
Language C++ (GCC 9.2.1)
Score 500
Code Size 1169 Byte
Status AC
Exec Time 600 ms
Memory 44432 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 53
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt AC 7 ms 3576 KiB
001.txt AC 2 ms 3396 KiB
002.txt AC 2 ms 3584 KiB
003.txt AC 2 ms 3528 KiB
004.txt AC 2 ms 3548 KiB
005.txt AC 597 ms 43956 KiB
006.txt AC 597 ms 44064 KiB
007.txt AC 595 ms 44072 KiB
008.txt AC 598 ms 44364 KiB
009.txt AC 593 ms 44060 KiB
010.txt AC 596 ms 44080 KiB
011.txt AC 597 ms 44428 KiB
012.txt AC 594 ms 44068 KiB
013.txt AC 597 ms 44000 KiB
014.txt AC 593 ms 44424 KiB
015.txt AC 596 ms 44000 KiB
016.txt AC 597 ms 44016 KiB
017.txt AC 594 ms 43972 KiB
018.txt AC 597 ms 43932 KiB
019.txt AC 595 ms 44028 KiB
020.txt AC 597 ms 44424 KiB
021.txt AC 594 ms 44060 KiB
022.txt AC 600 ms 43932 KiB
023.txt AC 594 ms 43920 KiB
024.txt AC 595 ms 43952 KiB
025.txt AC 596 ms 44016 KiB
026.txt AC 596 ms 43932 KiB
027.txt AC 593 ms 44120 KiB
028.txt AC 598 ms 44424 KiB
029.txt AC 597 ms 44012 KiB
030.txt AC 596 ms 44368 KiB
031.txt AC 595 ms 44428 KiB
032.txt AC 2 ms 3584 KiB
033.txt AC 2 ms 3580 KiB
034.txt AC 2 ms 3520 KiB
035.txt AC 599 ms 44432 KiB
036.txt AC 592 ms 44016 KiB
037.txt AC 596 ms 44428 KiB
038.txt AC 595 ms 43952 KiB
039.txt AC 597 ms 44016 KiB
040.txt AC 595 ms 43956 KiB
041.txt AC 594 ms 43956 KiB
042.txt AC 596 ms 43936 KiB
043.txt AC 594 ms 43952 KiB
044.txt AC 594 ms 44032 KiB
045.txt AC 598 ms 44364 KiB
046.txt AC 597 ms 44120 KiB
047.txt AC 595 ms 43952 KiB
048.txt AC 596 ms 44016 KiB
049.txt AC 593 ms 44064 KiB
example0.txt AC 4 ms 3480 KiB
example1.txt AC 2 ms 3608 KiB
example2.txt AC 600 ms 44016 KiB