結果

問題 No.4 おもりと天秤
ユーザー NiwakaNiwaka
提出日時 2022-03-23 00:48:37
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 253 ms / 5,000 ms
コード長 4,879 bytes
コンパイル時間 4,001 ms
コンパイル使用メモリ 144,984 KB
実行使用メモリ 21,888 KB
最終ジャッジ日時 2024-10-10 19:50:10
合計ジャッジ時間 6,184 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 3 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 3 ms
6,820 KB
testcase_05 AC 212 ms
19,328 KB
testcase_06 AC 1 ms
6,820 KB
testcase_07 AC 230 ms
20,480 KB
testcase_08 AC 1 ms
6,820 KB
testcase_09 AC 4 ms
6,816 KB
testcase_10 AC 253 ms
21,888 KB
testcase_11 AC 1 ms
6,820 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 2 ms
6,816 KB
testcase_14 AC 2 ms
6,820 KB
testcase_15 AC 2 ms
6,820 KB
testcase_16 AC 2 ms
6,816 KB
testcase_17 AC 2 ms
6,816 KB
testcase_18 AC 99 ms
11,520 KB
testcase_19 AC 198 ms
18,304 KB
testcase_20 AC 195 ms
18,048 KB
testcase_21 AC 184 ms
17,408 KB
testcase_22 AC 196 ms
18,176 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <sstream>
#include <set>
#include<stack>
#include <utility>
#include <tuple>
#include <unordered_map>
#include <string.h>
#include <iomanip>
#include <deque>
#include <climits>
#include <list>
#include <bitset>
//const long long MOD = 1000000000+7;
//const long long MOD = 998244353;
const long long MAX = 1000000000000000001;
//const long long MOD = 1000000000000000007;

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;
#define INF (llong)1<<60
#define DEBUG cout << "Hello" << endl;
//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//sort(s.begin(), s.end(), greater<char>())
//size()	文字数を返す
//Insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//c_str()変換
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());
//map<type, type> dict;で宣言
//グラフ理論用変数
//vector<vector<llong> > graph(N);

//ソート
//降順sort(v.begin(), v.end(), std::greater<Type>());

//大文字から小文字へんかん
//w[i] = w[i]-'A'+'a';

//vector
//assignメソッド　引数：サイズ、値
//与えられたサイズと値でvectorを初期化する

//queueクラス
//find()次に取り出す値の表示をする。
//pop()値を取り出す。戻り値はなし
//push()キューに値をプッシュする

//priority_queueクラス

//切り上げ
//ceil
//floor

//size()で返すのは、符号無し整数
//vectorが0の時は、
//for(int k=0; k<(int)temp_list.size()-1; k++)

/***
vector<llong> v;
do{

}while(next_permutation(v.begin(), v.end()));
***/

//二分探索カンニング
/***
llong right, left, middle;
right = 2e9;//2000000000
left  = 0;
while (right-left>1){
    middle = left + (right - left) / 2;
***/

//double型
//小数点以下10桁
//printf("%.10lf\n", ans);


/***
//const llong mod = 1000000007;
//const llong mod = 998244353;
class mint {
    public:
        llong x; // typedef long long llong;
        mint(llong x=0):x((x%mod+mod)%mod){}
        mint operator-() const { return mint(-x);}
        mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
        }
        mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
        }
        mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
        mint operator+(const mint a) const { return mint(*this) += a;}
        mint operator-(const mint a) const { return mint(*this) -= a;}
        mint operator*(const mint a) const { return mint(*this) *= a;}
        mint pow(llong t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
        }

        // for prime mod
        mint inv() const { return pow(mod-2);}
        mint& operator/=(const mint a) { return *this *= a.inv();}
        mint operator/(const mint a) const { return mint(*this) /= a;}
};
***/

/***
llong dfs(llong i, llong n, llong N, vector<vector<llong>>& dp){
    if(i==N){
        return 1;
    }
    if(dp[i][n]!=-1){
        return dp[i][n];
    }
    mint total=0;
    if(n-1>=1)total += dfs(i+1, n-1, N, dp);
    total += dfs(i+1, n, N, dp);
    if(n+1<=9)total += dfs(i+1, n+1, N, dp);
    return dp[i][n]=total.x;
}
***/
//llong dx[4] = { 0, 1, 0, -1 };
//llong dy[4] = { 1, 0, -1, 0 };

llong N;
llong total=0;//Aグループの総和
bool dfs(llong i, llong sum, vector<llong>& W, map<pair<llong, llong>, bool>& dp){
    bool ans=false;
    if(i==N){
        return sum==total;
    }
    if(dp.count({i, sum})!=0){
        return dp[{i, sum}];
    }
    ans = dfs(i+1, sum+W[i], W, dp)|dfs(i+1, sum, W, dp);
    return dp[{i, sum}]=ans;
}

int main(){ 
    cin >> N;
    vector<llong> W(N);
    for(int i=0; i<N; i++){
        cin >> W[i];
        total+=W[i];
    }
    if(total%2!=0){
        cout << "impossible" << endl;
        return 0;
    }
    map<pair<llong, llong>, bool> dp;
    total/=2;
    cout << ((dfs(1, W[0], W, dp)|dfs(1, 0, W, dp))?"possible":"impossible") << endl;
}
0