#943380 (C++17) No.2603 Tone Correction

• 問題: No.2603 Tone Correction
• ユーザー: 沙耶花
• 提出日時: 2024-01-12 22:02:30
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 964 ms / 2,000 ms
• コード長: 981 bytes
• コンパイル時間: 5,479 ms
• コンパイル使用メモリ: 264,892 KB
• 実行使用メモリ: 9,476 KB
• 最終ジャッジ日時: 2024-01-12 22:03:05
• 合計ジャッジ時間: 28,288 ms
• ジャッジサーバーID （参考情報）: judge14 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,676 KB
testcase_01	AC	2 ms; 6,676 KB
testcase_02	AC	2 ms; 6,676 KB
testcase_03	AC	19 ms; 6,676 KB
testcase_04	AC	17 ms; 6,676 KB
testcase_05	AC	16 ms; 6,676 KB
testcase_06	AC	15 ms; 6,676 KB
testcase_07	AC	16 ms; 6,676 KB
testcase_08	AC	16 ms; 6,676 KB
testcase_09	AC	16 ms; 6,676 KB
testcase_10	AC	16 ms; 6,676 KB
testcase_11	AC	16 ms; 6,676 KB
testcase_12	AC	16 ms; 6,676 KB
testcase_13	AC	958 ms; 9,476 KB
testcase_14	AC	930 ms; 9,476 KB
testcase_15	AC	954 ms; 9,476 KB
testcase_16	AC	956 ms; 9,476 KB
testcase_17	AC	958 ms; 9,476 KB
testcase_18	AC	942 ms; 9,476 KB
testcase_19	AC	953 ms; 9,476 KB
testcase_20	AC	957 ms; 9,476 KB
testcase_21	AC	964 ms; 9,476 KB
testcase_22	AC	952 ms; 9,476 KB
testcase_23	AC	935 ms; 9,476 KB
testcase_24	AC	935 ms; 9,476 KB
testcase_25	AC	942 ms; 9,476 KB
testcase_26	AC	948 ms; 9,476 KB
testcase_27	AC	920 ms; 9,476 KB
testcase_28	AC	933 ms; 9,476 KB
testcase_29	AC	954 ms; 9,476 KB
testcase_30	AC	951 ms; 9,476 KB
testcase_31	AC	925 ms; 9,476 KB
testcase_32	AC	949 ms; 9,476 KB
testcase_33	AC	2 ms; 6,676 KB
testcase_34	AC	942 ms; 9,476 KB
testcase_35	AC	963 ms; 9,476 KB

ソースコード

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 1000000000000000001


int main(){
	
	long long n,m;
	cin>>n>>m;
	vector<long long> a(n),b(n);
	rep(i,n)scanf("%lld",&a[i]);
	rep(i,n)scanf("%lld",&b[i]);
	
	rep(i,n){
		a[i] -= b[i];
		a[i] += m;
		a[i] %= m;
	}
	a.insert(a.begin(),0LL);
	a.push_back(0);
	vector<long long> dp(600,Inf64);
	dp[dp.size()/2] = 0;
	for(int i=1;i<a.size();i++){
		vector<long long> ndp(600,Inf64);
		rep(j,dp.size()){
			long long x = a[i-1];
			x -= m*(dp.size()/2);
			x += m*j;
			for(int k = -1;k<=1;k++){
				if(j+k<0||j+k>=dp.size())continue;
				long long y = a[i];
				y -= m*(dp.size()/2);
				y += m*j;
				y += m*k;
				ndp[j+k] = min(ndp[j+k],dp[j] + abs(x-y));
			}
			
		}
		swap(dp,ndp);
	}
	long long ans = dp[dp.size()/2];
	cout<<ans/2<<endl;
	return 0;
}