結果
問題 | No.2114 01 Matching |
ユーザー |
![]() |
提出日時 | 2022-10-19 04:34:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 521 ms / 5,000 ms |
コード長 | 3,034 bytes |
コンパイル時間 | 5,594 ms |
コンパイル使用メモリ | 290,260 KB |
最終ジャッジ日時 | 2025-02-08 08:15:14 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 51 |
ソースコード
#if defined(LOCAL)#include<stdc++.h>#else#include<bits/stdc++.h>#endif#include<random>#pragma GCC optimize("Ofast")//#pragma GCC target("avx2")#pragma GCC optimize("unroll-loops")using namespace std;//#include<boost/multiprecision/cpp_int.hpp>//#include<boost/multiprecision/cpp_dec_float.hpp>//namespace mp=boost::multiprecision;//#define mulint mp::cpp_int//#define mulfloat mp::cpp_dec_float_100struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;//#define INF (1<<30)#define LINF (lint)(1LL<<56)#define MINF (lint)(2e18)#define endl "\n"#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)#define flc(x) __builtin_popcountll(x)#define pint pair<int,int>#define pdouble pair<double,double>#define plint pair<lint,lint>#define fi first#define se second#define all(x) x.begin(),x.end()//#define vec vector<lint>#define nep(x) next_permutation(all(x))typedef long long lint;int dx[8]={1,1,0,-1,-1,-1,0,1};int dy[8]={0,1,1,1,0,-1,-1,-1};const int MAX_N=3e5+5;template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}//vector<int> bucket[MAX_N/1000];//constexpr int MOD=1000000007;constexpr int MOD=998244353;#include<atcoder/all>using namespace atcoder;typedef __int128_t llint;lint op(lint a,lint b){return min(a,b);}lint e(){return 1e18;}lint mapping(lint f,lint x){return f+x;}lint composition(lint f,lint g){return f+g;}lint id(){return 0;}lint solve(vector<lint> R,vector<lint> B,lint K){lint N=R.size(),M=B.size();vector<pair<lint,bool>> balls;rep(i,N) balls.push_back({R[i],1});rep(i,M) balls.push_back({B[i],0});sort(all(balls));lazy_segtree<lint,op,e,lint,mapping,composition,id> dp(N+M+1);int zero=N;dp.set(zero,0);for(auto e:balls){lint num=e.fi;bool color=e.se;if(color){ //赤が来た場合 捨てるのは不可dp.apply(0,zero,num);dp.apply(zero,N+M+1,-num);zero--;}else{ //青が来た場合lint sv=dp.prod(zero,zero+1);dp.apply(0,zero+1,-num);dp.apply(zero+1,N+M+1,num);dp.set(zero+1,min(sv,dp.prod(zero+1,zero+2)));zero++;}}return dp.prod(zero,zero+1)/K;}int main(void){lint N,M,K;cin >> N >> M >> K;vector<lint> B(N),R(M);rep(i,N) cin >> B[i];rep(i,M) cin >> R[i];if(N<M) swap(N,M),swap(B,R);map<int,pair<vector<lint>,vector<lint>>> mp;rep(i,N) mp[B[i]%K].fi.push_back(B[i]);rep(i,M) mp[R[i]%K].se.push_back(R[i]);lint ans=0;for(auto e:mp){vector<lint> b=e.se.fi;vector<lint> r=e.se.se;if(b.size()<r.size()){cout << -1 << endl;return 0;}if(r.size()) ans+=solve(r,b,K);}cout << ans << endl;}