解法 二分探索 + 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); }