結果
問題 | No.532 Possible or Impossible |
ユーザー |
|
提出日時 | 2023-02-12 20:51:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 810 bytes |
コンパイル時間 | 1,565 ms |
コンパイル使用メモリ | 172,396 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-16 06:47:26 |
合計ジャッジ時間 | 2,393 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; if(n == 2 && m == 2){ cout << "Possible" << '\n'; return 0; } vector<vector<bool>> dp(n + 1, vector<bool>(200001)); dp[1][100001] = true; for(int i = 1; i < n; i++){ int v = i + 1; for(int j = 0; j <= 200000; j++){ if(!dp[i][j])continue; dp[i + 1][j] = true; if(j + v <= 200000) dp[i + 1][j + v] = true; if(j - v >= 0) dp[i + 1][j - v] = true; ll v = j - 100000; if(-100000 <= v * j && v * j <= 100000) dp[i + 1][v * j + 100000] = true; } } cout << (dp[n][m + 100000] ? "Possible" : "Impossible") << '\n'; }