解法 二分探索 + bfs 自分で支払う上限で二分探索する 判定方法は上限より大きい辺のコストを1、上限以下の辺のコストを0としたグラフ上でbfs コストk以下で到達できればok const int inf = ten(9); int n, p, k; vector<pint> e[1024]; bool bfs(int pay_upper) {</pint>…

状態が(経過時間, exaustion)のdp int main() { int n, m; int d[ten(4)]; scanf("%d%d", &n, &m); rep(i, n) scanf("%d", d + i); static int dp[ten(4) + 1000][512]; rep(i, n) { erep(j, m) { // run chmax(dp[i + 1][j + 1], dp[i][j] + d[i]); // rest…

解法 入力から有向グラフを作る。AがBに勝ったという情報からA -> Bに辺を張る このグラフ上でiからjに到達可能ならば、iはjに勝てるn cows中でiがkthの時、iは(n - k)cowsにwin and iは(k - 1)cowsにlose 順位が決定できる場合、win + lose == (n - k) + (k…

問題の解釈をがんばる int main() { int n, t; scanf("%d%d", &n, &t); if (n == 1) { while (t--) puts("1"); return 0; } pint song[2000]; rep(i, n) { song[i].second = -(i + 1); scanf("%d", &song[i].first); } while (t--) { sort(song, song + n, g…

やるだけ int main() { int n, k; scanf("%d%d", &n, &k); pint a[5 * ten(4)], b[5 * ten(4)]; rep(i, n) { scanf("%d%d", &a[i].first, &b[i].first); a[i].second = b[i].second = i + 1; } sort(a, a + n, greater<pint>()); sort(b, b + n, greater<pint>()); bool </pint></pint>…

二分探索する int main() { int n, s; scanf("%d%d", &n, &s); int l[2 * ten(4)]; rep(i, n) scanf("%d", l + i); sort(l, l + n); int res = 0; rep(i, n) res += upper_bound(l, l + i, s - l[i]) - l; printf("%d\n", res); }

本番の結果 xoo--- 249位 1808 -> 1758 Aにハマったまま終了(´・ω・`) A Cinema 解法 各映画のfavorite actorsの上限と下限を求めて、後は題意通りに実装 ソースコード int main() { #ifdef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output…

解けるまで 2^25のdp(char dp[1 枝狩り + unordered_mapなどゴリ押ししようとするがMLE取れず 2^25以上の配列を確保して通っている人がいるのに謎実は工夫すれば2^25の状態のdpで通せる 求めたい最大の答えは16未満なので、1つの状態に対して4bitあれば十分 …

Easy GreatFairyWar やるだけ int GreatFairyWar::minHP(vector <int> dps, vector <int> hp) { int dame = 0; for (int i = 0, t = 0; i < dps.size(); ++i) { t += hp[i]; dame += dps[i] * t; } return dame; } Medium IncubatorEasy n int IncubatorEasy::maxMagic</int></int>…

とりあえず作って長い間放置してました コード貼っつけるだけでもがんばって書いていきたい

TopCoder, Codeforces, AOJなどで解いた問題の解法を書いていく予定