結果
問題 | No.2542 Yokan for Two |
ユーザー |
![]() |
提出日時 | 2023-11-24 21:30:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 930 bytes |
コンパイル時間 | 4,298 ms |
コンパイル使用メモリ | 254,696 KB |
最終ジャッジ日時 | 2025-02-17 23:46:25 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 int main(){ int L,N; cin>>L>>N; vector<long long> x(N); rep(i,N)cin>>x[i]; x.push_back(L); N++; for(int i=N-1;i>=1;i--)x[i] -= x[i-1]; int A = x[0]-x.back(); x.erase(x.begin()); x.pop_back(); N -= 2; vector dp(2,vector<bool>(L*2+5,false)); int mid = L+1; dp[0][mid] = true; rep(i,N){ vector ndp(2,vector<bool>(L*2+5,false)); rep(j,2){ rep(k,L*2+5){ if(dp[j][k]==false)continue; ndp[0][k+x[i]] = true; ndp[1][k+x[i]] = true; ndp[0][k-x[i]] = true; ndp[1][k-x[i]] = true; } } swap(dp,ndp); } int ans = Inf32; rep(i,L*2+5){ if(dp[0][i])ans = min(ans,abs(i-mid+A)); } cout<<ans<<endl; return 0; }