oj.uz

Submission #958059

# Submission time Handle Problem Language Result Execution time Memory
958059 2024-04-04T20:05:35 Z shadow_sami Collecting Stamps 3 (JOI20_ho_t3) C++17
5 / 100
 288 ms 354264 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
const ll mxn = 13;
const ll mxm = 200+5;
ll dp[1<<mxn][mxn][mxm];
ll a[mx];
ll b[mx];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

		cin>>n>>m;
		fip(0,n)
			cin>>a[i];
		fip(0,n)
			cin>>b[i];
		fip(0,1<<n){
			fjp(0,n){
				fp(k,0,mxm){
					dp[i][j][k] = -1e18;
				}
			}
		}
		fip(0,n){
			dp[1<<i][i][a[i]] = max((ll)(a[i]<=b[i]),dp[1<<i][i][a[i]]);
			dp[1<<i][i][m-a[i]] = max((ll)((m-a[i])<=b[i]),dp[1<<i][i][m-a[i]]);
		}
		fip(1,(1<<n)){
			fjp(0,n){
				if(i&(1<<j))
					continue;
				fp(k,0,n){
					if(i&(1<<k)){
						fp(t,0,200+1){
							if(t+abs(a[k]-a[j])<mxm)
								dp[i|(1<<j)][j][t+abs(a[k]-a[j])] = max(dp[i|(1<<j)][j][t+abs(a[k]-a[j])],dp[i][k][t]+((t+abs(a[k]-a[j]))<=b[j]));
							if(t+m-abs(a[k]-a[j])<mxm)
								dp[i|(1<<j)][j][t+m-abs(a[k]-a[j])] = max(dp[i|(1<<j)][j][t+m-abs(a[k]-a[j])],dp[i][k][t]+((t+m-abs(a[k]-a[j]))<=b[j]));
						}							
					}
				}
			}
		}
		ans = -1e18;
		fip(0,(1<<n))
			fjp(0,n)
				fp(k,0,201)
					ans = max(ans,dp[i][j][k]);
		cout<<ans<<nli;
        
    cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 7 ms 14684 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 103 ms 90708 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 16 ms 27112 KB Output is correct
9 Correct 82 ms 90716 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 93 ms 90720 KB Output is correct
13 Correct 101 ms 90732 KB Output is correct
14 Correct 2 ms 8536 KB Output is correct
15 Correct 4 ms 10588 KB Output is correct
16 Correct 89 ms 90732 KB Output is correct
17 Correct 90 ms 90732 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 7 ms 14684 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 103 ms 90708 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 16 ms 27112 KB Output is correct
9 Correct 82 ms 90716 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 93 ms 90720 KB Output is correct
13 Correct 101 ms 90732 KB Output is correct
14 Correct 2 ms 8536 KB Output is correct
15 Correct 4 ms 10588 KB Output is correct
16 Correct 89 ms 90732 KB Output is correct
17 Correct 90 ms 90732 KB Output is correct
18 Runtime error 214 ms 354244 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 7 ms 14684 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 103 ms 90708 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 16 ms 27112 KB Output is correct
9 Correct 82 ms 90716 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 93 ms 90720 KB Output is correct
13 Correct 101 ms 90732 KB Output is correct
14 Correct 2 ms 8536 KB Output is correct
15 Correct 4 ms 10588 KB Output is correct
16 Correct 89 ms 90732 KB Output is correct
17 Correct 90 ms 90732 KB Output is correct
18 Runtime error 288 ms 354264 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 7 ms 14684 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 103 ms 90708 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 16 ms 27112 KB Output is correct
9 Correct 82 ms 90716 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 93 ms 90720 KB Output is correct
13 Correct 101 ms 90732 KB Output is correct
14 Correct 2 ms 8536 KB Output is correct
15 Correct 4 ms 10588 KB Output is correct
16 Correct 89 ms 90732 KB Output is correct
17 Correct 90 ms 90732 KB Output is correct
18 Runtime error 214 ms 354244 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -