結果

問題 No.1060 素敵な宝箱
ユーザー ok
提出日時 2020-05-22 22:42:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,446 bytes
コンパイル時間 947 ms
コンパイル使用メモリ 90,380 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-10-05 19:11:10
合計ジャッジ時間 4,653 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
#define int long long
#define endl "\n"
constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 
struct fast_io {
    fast_io(){
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
    };
} fio;
int ans;
int N, M;
vector<vector<int>> A;
vector<vector<int>> X;
vector<int> used;
int rec(int depth = 0){ //cout<<depth<<endl;
    
    if(depth == N) {
        int sum = 0;
    for(int j = 0; j < M; j++){
        sum += (X[0][j] * X[0][j]) - (X[1][j] * X[1][j]);
    }
        
        ans = max(ans, sum);
        
        return sum;
    } else {
        // if(depth%2 == 0 && ans < sum) return -INF;
    }
    
    
    int maximum = -INF, minimum = INF;
    
    for(int i = 0; i < N; i++){
        if(used[i]) continue;
        used[i] = true;
        
        // X[depth][i]
        for(int j = 0; j < M; j++){
            X[depth%2][j] += A[i][j];
        }
        
        int temp = rec(depth+1);
        
        maximum = max(temp, maximum);
        minimum = min(temp, minimum);
        
        for(int j = 0; j < M; j++){
            X[depth%2][j] -= A[i][j];
        }
        
        used[i] = false;
    }
    
    if(depth%2 == 0) return maximum;
    return minimum;
}
signed main(){
    cout<<fixed<<setprecision(10);
    
    cin>>N>>M;
    
    A.resize(N, vector<int>(M));
    X.resize(2, vector<int>(M));
    used.resize(N);
    
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin>>A[i][j];
        }
    }
    
    ans = rec();
    
    cout<<ans<<endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0