提出 #48959505

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f'3f3f3f3f;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
const int C = 300;
int main(){
  int n=read(); // 300
  ll h=read(); // 1e18
  vector<array<ll,2> > cd(n); // -300~300, 1e9
  rep(i,0,n) {
    cd[i][0]=read();
    cd[i][1]=read();
  }
  auto setMax=[](auto&a,auto b){ a=max(a,b); };
  // dp[个数][c的和]=最大伤害,最优方案总能切割长个数<=2C,前缀保持<=2C的多个段
  vector dp(2*C+1,vector<ll>(2*C+1,-INF));
  dp[0][0] = 0;
  vector<ll> D(2*C+1,-INF); // D[个数] = 最大伤害, 2*300*1e9
  rep(j,0,2*C) for(auto [c,d]:cd) rep(s,0,2*C+1) if(dp[j][s] != -INF) // 先for个数
      if(s - c >= 0 and s - c <= 2*C) setMax(dp[j+1][s-c], dp[j][s]+d);
  rep(j,0,2*C+1) rep(s,0,2*C+1) if(dp[j][s] != -INF) setMax(D[j], dp[j][s]);
  int besti = 1;
  rep(i,2,2*C+1) if(D[i]*besti > D[besti]*i) besti = i; // D[i]/i > D[besti]/besti, 600^2*1e9
  const int mxS = (2*C*2*C);
  vector dp2(mxS+1,-INF); // dp2[代价和j <= 2C*2C] = 最大伤害
  dp2[0] = 0;
  ll ans = INF;
  rep(i,1,2*C+1) rep(j,0,mxS) if(dp2[j] != -INF) if(j + i <= mxS) setMax(dp2[j+i],min(dp2[j]+D[i],INF));
  auto ceildiv=[](ll a,ll b){return a/b+!!(a%b);};
  rep(j,1,mxS+1) if(dp2[j] != -INF) {
    if(dp2[j] >= h) ans = min(ans,j);
    else            ans = min(ans,j+ceildiv(h-dp2[j],D[besti])*besti);
  }

  printf("%lld\n",ans);
  return 0;
}

提出情報

提出日時
問題 Ex - Negative Cost
ユーザ cromarmot
言語 C++ 20 (gcc 12.2)
得点 625
コード長 1477 Byte
結果 AC
実行時間 315 ms
メモリ 9168 KiB

コンパイルエラー

Main.cpp: In function ‘ll read()’:
Main.cpp:6:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    6 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 625 / 625
結果
AC × 2
AC × 91
セット名 テストケース
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, 064.txt, 065.txt, 066.txt, 067.txt, 068.txt, 069.txt, 070.txt, 071.txt, 072.txt, 073.txt, 074.txt, 075.txt, 076.txt, 077.txt, 078.txt, 079.txt, 080.txt, 081.txt, 082.txt, 083.txt, 084.txt, 085.txt, 086.txt, 087.txt, 088.txt, example0.txt, example1.txt
ケース名 結果 実行時間 メモリ
000.txt AC 189 ms 9044 KiB
001.txt AC 193 ms 9044 KiB
002.txt AC 259 ms 9056 KiB
003.txt AC 256 ms 8968 KiB
004.txt AC 244 ms 9152 KiB
005.txt AC 262 ms 9080 KiB
006.txt AC 200 ms 9156 KiB
007.txt AC 275 ms 9000 KiB
008.txt AC 228 ms 9060 KiB
009.txt AC 275 ms 9056 KiB
010.txt AC 299 ms 9044 KiB
011.txt AC 272 ms 9028 KiB
012.txt AC 278 ms 9040 KiB
013.txt AC 275 ms 9168 KiB
014.txt AC 279 ms 9044 KiB
015.txt AC 286 ms 9040 KiB
016.txt AC 273 ms 9056 KiB
017.txt AC 274 ms 9084 KiB
018.txt AC 275 ms 9068 KiB
019.txt AC 272 ms 9040 KiB
020.txt AC 276 ms 9068 KiB
021.txt AC 274 ms 9044 KiB
022.txt AC 275 ms 9072 KiB
023.txt AC 275 ms 9160 KiB
024.txt AC 273 ms 9156 KiB
025.txt AC 273 ms 9076 KiB
026.txt AC 291 ms 9000 KiB
027.txt AC 275 ms 9064 KiB
028.txt AC 282 ms 8928 KiB
029.txt AC 193 ms 8928 KiB
030.txt AC 194 ms 9072 KiB
031.txt AC 193 ms 8932 KiB
032.txt AC 193 ms 9020 KiB
033.txt AC 195 ms 9036 KiB
034.txt AC 195 ms 8936 KiB
035.txt AC 195 ms 9060 KiB
036.txt AC 193 ms 9020 KiB
037.txt AC 194 ms 8932 KiB
038.txt AC 193 ms 9060 KiB
039.txt AC 195 ms 9072 KiB
040.txt AC 222 ms 9088 KiB
041.txt AC 193 ms 9060 KiB
042.txt AC 194 ms 9052 KiB
043.txt AC 193 ms 9000 KiB
044.txt AC 232 ms 9092 KiB
045.txt AC 194 ms 9028 KiB
046.txt AC 193 ms 9056 KiB
047.txt AC 192 ms 9040 KiB
048.txt AC 234 ms 9084 KiB
049.txt AC 200 ms 9040 KiB
050.txt AC 286 ms 9004 KiB
051.txt AC 226 ms 9156 KiB
052.txt AC 204 ms 9052 KiB
053.txt AC 197 ms 9056 KiB
054.txt AC 252 ms 9040 KiB
055.txt AC 313 ms 9056 KiB
056.txt AC 257 ms 9088 KiB
057.txt AC 283 ms 9056 KiB
058.txt AC 266 ms 9064 KiB
059.txt AC 295 ms 9052 KiB
060.txt AC 288 ms 9068 KiB
061.txt AC 290 ms 9024 KiB
062.txt AC 288 ms 9004 KiB
063.txt AC 289 ms 9040 KiB
064.txt AC 286 ms 9064 KiB
065.txt AC 291 ms 9028 KiB
066.txt AC 289 ms 9160 KiB
067.txt AC 290 ms 9032 KiB
068.txt AC 291 ms 9060 KiB
069.txt AC 290 ms 9156 KiB
070.txt AC 290 ms 9008 KiB
071.txt AC 302 ms 9052 KiB
072.txt AC 288 ms 9040 KiB
073.txt AC 288 ms 9152 KiB
074.txt AC 289 ms 9024 KiB
075.txt AC 288 ms 9068 KiB
076.txt AC 307 ms 9036 KiB
077.txt AC 288 ms 9004 KiB
078.txt AC 288 ms 9088 KiB
079.txt AC 289 ms 8936 KiB
080.txt AC 293 ms 8972 KiB
081.txt AC 290 ms 9068 KiB
082.txt AC 291 ms 9028 KiB
083.txt AC 289 ms 9168 KiB
084.txt AC 315 ms 9040 KiB
085.txt AC 291 ms 9072 KiB
086.txt AC 290 ms 9068 KiB
087.txt AC 290 ms 9072 KiB
088.txt AC 288 ms 9160 KiB
example0.txt AC 195 ms 9160 KiB
example1.txt AC 204 ms 9084 KiB