結果
問題 | 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';}