Submission #940917

#	Time	Username	Problem	Language	Result	Execution time	Memory
940917		LittleOrange	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	3581 ms	1048576 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,l;
    cin >> n >> l;
    vector<ll> x(n),t(n);
    for(ll &i : x) cin >> i;
    for(ll &i : t) cin >> i;
    vector<vector<ll>> dp(1<<n,vector<ll>(n,big));
    for(ll i = 0;i<n;i++){
        ll d = min(x[i],l-x[i]);
        if(d<=t[i]){
            dp[1<<i][i] = d;
        }
    }
    ll ans = 0;
    for(ll i = 1;i<(1<<n);i++){
        for(ll j = 0;j<n;j++) if(i>>j&1){
            for(ll k = 0;k<n;k++) if(i>>k&1^1){
                ll dd = abs(x[j]-x[k]);
                ll d = dp[i][j]+min(dd,l-dd);
                if (d<=t[k]){
                    dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k],d);
                }
            }
            if(dp[i][j]<big) ans = max(ans,(ll)__builtin_popcountll(i));
        }
    }
    cout << ans << "\n";
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:22:42: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   22 |             for(ll k = 0;k<n;k++) if(i>>k&1^1){
      |                                      ~~~~^~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75