結果
問題 | No.949 飲酒プログラミングコンテスト |
ユーザー |
|
提出日時 | 2019-12-12 02:57:52 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,500 ms |
コード長 | 1,441 bytes |
コンパイル時間 | 386 ms |
コンパイル使用メモリ | 39,372 KB |
実行使用メモリ | 72,212 KB |
最終ジャッジ日時 | 2024-06-24 08:16:15 |
合計ジャッジ時間 | 2,411 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:12:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 12 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:13:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 13 | for (int i = 0; i <= n; i++) scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:14:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 14 | for (int i = 0; i <= n; i++) scanf("%d", &b[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:15:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 15 | for (int i = 1; i <= n; i++) scanf("%d", &d[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <stdio.h> #include <algorithm> #include <utility> using namespace std; #define F first #define S second constexpr int kN = int(3E3 + 10); pair<int, int> dp[kN][kN]; int a[kN], b[kN], d[kN]; int main() { int n; scanf("%d", &n); for (int i = 0; i <= n; i++) scanf("%d", &a[i]); for (int i = 0; i <= n; i++) scanf("%d", &b[i]); for (int i = 1; i <= n; i++) scanf("%d", &d[i]); sort(d + 1, d + n + 1); reverse(d + 1, d + n + 1); dp[0][0] = {0, 1}; for (int i = 1; i <= n; i++) { dp[0][i] = dp[0][i - 1]; while (dp[0][i].S <= n && a[0] + b[i] < d[dp[0][i].S]) dp[0][i].S++; if (dp[0][i].S <= n && a[0] + b[i] >= d[dp[0][i].S]) { dp[0][i].F++; dp[0][i].S++; } } for (int i = 1; i <= n; i++) { dp[i][0] = dp[i - 1][0]; while (dp[i][0].S <= n && a[i] + b[0] < d[dp[i][0].S]) dp[i][0].S++; if (dp[i][0].S <= n && a[i] + b[0] >= d[dp[i][0].S]) { dp[i][0].F++; dp[i][0].S++; } for (int j = 1; j <= n; j++) { if (dp[i - 1][j].F > dp[i][j - 1].F) dp[i][j] = dp[i - 1][j]; else if (dp[i - 1][j].F < dp[i][j - 1].F) dp[i][j] = dp[i][j - 1]; else if (dp[i - 1][j].S < dp[i][j - 1].S) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i][j - 1]; while (dp[i][j].S <= n && a[i] + b[j] < d[dp[i][j].S]) dp[i][j].S++; if (dp[i][j].S <= n && a[i] + b[j] >= d[dp[i][j].S]) { dp[i][j].F++; dp[i][j].S++; } } } printf("%d\n", dp[n][n].F); }