結果
問題 | No.1324 Approximate the Matrix |
ユーザー |
![]() |
提出日時 | 2020-11-30 23:15:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,938 bytes |
コンパイル時間 | 2,570 ms |
コンパイル使用メモリ | 202,896 KB |
最終ジャッジ日時 | 2025-01-16 10:35:25 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 RE * 2 TLE * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(ll i=0;i<(ll)n;i++) #define dump(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << (x) << "\n"; #define spa << " " << #define fi first #define se second #define ALL(a) (a).begin(),(a).end() #define ALLR(a) (a).rbegin(),(a).rend() using ld = long double; using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; template<typename T> using V = vector<T>; template<typename T> using P = pair<T, T>; template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); } template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); } template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){os << "(" << v.first << ", " << v.second << ")"; return os;} template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; } template<class T> ostream& operator<<(ostream& os, const vector<vector<T>> &v){ for(auto &e : v){os << e << "\n";} return os;} struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; template <class T> void UNIQUE(vector<T> &x) {sort(ALL(x));x.erase(unique(ALL(x)), x.end());} 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 (a>b) { a=b; return 1; } return 0; } void fail() { cout << -1 << '\n'; exit(0); } inline int popcount(const int x) { return __builtin_popcount(x); } inline int popcount(const ll x) { return __builtin_popcountll(x); } template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++) {cerr<<v[i][0];for(ll j=1;j<w;j++)cerr spa v[i][j];cerr<<"\n";}}; template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cerr<<v[0]; for(ll i=1;i<n;i++)cerr spa v[i]; cerr<<"\n";}; const ll INF = (1ll<<62); // const ld EPS = 1e-10; // const ld PI = acos(-1.0); const ll mod = (int)1e9 + 7; //const ll mod = 998244353; int main(){ int N, M; std::cin >> N >> M; std::vector<int> A(N), B(N); for(int i=0;i<N;i++) std::cin >> A[i]; for(int i=0;i<N;i++) std::cin >> B[i]; std::vector<std::vector<int>> T(N, std::vector<int>(N, 0)); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ std::cin >> T[i][j]; } } ll obj = INF; V<V<int>> sol(N, V<int>(N, 0)); V<V<int>> res; auto dfs = [&](auto self, int S, int ci, int cj)->void{ if(S<0) return; if(ci == N){ bool ok = true; for(int j=0;j<N;j++){ int col_sum = 0; for(int i=0;i<N;i++){ col_sum += sol[i][j]; } if(col_sum != B[j]) ok = false; } if(ok){ ll obj_tmp = 0; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ obj_tmp += (T[i][j] - sol[i][j])*(T[i][j] - sol[i][j]); } } if(chmin(obj, obj_tmp)){ // dump(sol) res = sol; } } return; } if(cj == 0){ for(int v=0;v<=A[ci];v++){ sol[ci][cj] = v; self(self, A[ci]-v, ci, cj+1); sol[ci][cj] = 0; } }else if(cj == N-1){ sol[ci][cj] = S; self(self, 0, ci+1, 0); sol[ci][cj] = 0; }else{ for(int v=0;v<=S;v++){ sol[ci][cj] = v; self(self, S-v, ci, cj+1); sol[ci][cj] = 0; } } }; dfs(dfs, 0, 0, 0); // cout << res << endl; cout << obj << endl; return 0; }