提出 #44028774

ソースコード 拡げる

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const ll MAXN = 310,INF = 2e18;

void tomax(ll& x,ll y){x = max(x,y);}
void tomin(ll& x,ll y){x = min(x,y);}

ll n,H,c[MAXN],d[MAXN],ans = INF;

ll dp[MAXN*2][MAXN*2],M = 605;

ll dp2[MAXN*MAXN*4];

ll val[MAXN*2];

vector<int>arr;

int main(){
	cin>>n>>H;

	rep(i,1,n){
		cin>>c[i]>>d[i];
	}

	rep(i,0,M)rep(j,0,M)dp[i][j] = -INF;

	dp[0][0] = 0;

	rep(i,0,M-1)rep(j,0,M)if(dp[i][j] != -INF){
		rep(k,1,n)if(j - c[k] >= 0 && j - c[k] <= M)tomax(dp[i+1][j-c[k]],dp[i][j] + d[k]);
	}

	rep(i,1,M){
		val[i] = -INF;
		rep(j,0,M)tomax(val[i],dp[i][j]);

		if(val[i] != -INF)arr.push_back(i);
	}


	int cnt = arr.size();assert(cnt);
	sort(arr.begin(),arr.end(),[&](int x,int y){return val[x] * y > val[y] * x;});

	int f = arr[0];

	rep(i,0,M*M)dp2[i] = -INF;
	dp2[0] = 0;
	rep(i,0,M*M-1)if(dp2[i] != -INF){
		rep(j,1,cnt-1){
			int x = arr[j];
			if(i + x <= M*M)tomax(dp2[i+x],dp2[i] + val[x]);
		}
	}
	rep(i,0,M*M)if(dp2[i] != -INF){
		ll rest = H - dp2[i],cnt = i;
		if(rest > 0)cnt += (rest + val[f] - 1) / val[f] * f;

		tomin(ans,cnt);
	}

	cout<<ans<<endl;

    return 0;
}

提出情報

提出日時
問題 Ex - Negative Cost
ユーザ Crying
言語 C++ (GCC 9.2.1)
得点 625
コード長 1538 Byte
結果 AC
実行時間 392 ms
メモリ 9452 KiB

ジャッジ結果

セット名 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 215 ms 9424 KiB
001.txt AC 215 ms 9384 KiB
002.txt AC 216 ms 9388 KiB
003.txt AC 15 ms 9440 KiB
004.txt AC 306 ms 9308 KiB
005.txt AC 316 ms 9304 KiB
006.txt AC 226 ms 9256 KiB
007.txt AC 362 ms 9228 KiB
008.txt AC 270 ms 9384 KiB
009.txt AC 301 ms 9388 KiB
010.txt AC 303 ms 9364 KiB
011.txt AC 300 ms 9380 KiB
012.txt AC 300 ms 9252 KiB
013.txt AC 303 ms 9248 KiB
014.txt AC 301 ms 9300 KiB
015.txt AC 300 ms 9380 KiB
016.txt AC 301 ms 9256 KiB
017.txt AC 304 ms 9428 KiB
018.txt AC 300 ms 9244 KiB
019.txt AC 301 ms 9340 KiB
020.txt AC 300 ms 9228 KiB
021.txt AC 301 ms 9428 KiB
022.txt AC 300 ms 9344 KiB
023.txt AC 301 ms 9224 KiB
024.txt AC 304 ms 9376 KiB
025.txt AC 298 ms 9228 KiB
026.txt AC 300 ms 9428 KiB
027.txt AC 301 ms 9304 KiB
028.txt AC 300 ms 9260 KiB
029.txt AC 212 ms 9452 KiB
030.txt AC 214 ms 9376 KiB
031.txt AC 214 ms 9380 KiB
032.txt AC 212 ms 9224 KiB
033.txt AC 214 ms 9428 KiB
034.txt AC 214 ms 9340 KiB
035.txt AC 214 ms 9364 KiB
036.txt AC 214 ms 9196 KiB
037.txt AC 214 ms 9196 KiB
038.txt AC 216 ms 9428 KiB
039.txt AC 215 ms 9380 KiB
040.txt AC 216 ms 9364 KiB
041.txt AC 216 ms 9360 KiB
042.txt AC 215 ms 9244 KiB
043.txt AC 215 ms 9344 KiB
044.txt AC 214 ms 9344 KiB
045.txt AC 213 ms 9192 KiB
046.txt AC 213 ms 9428 KiB
047.txt AC 213 ms 9340 KiB
048.txt AC 213 ms 9252 KiB
049.txt AC 227 ms 9252 KiB
050.txt AC 384 ms 9384 KiB
051.txt AC 269 ms 9244 KiB
052.txt AC 235 ms 9196 KiB
053.txt AC 222 ms 9384 KiB
054.txt AC 323 ms 9340 KiB
055.txt AC 370 ms 9428 KiB
056.txt AC 326 ms 9344 KiB
057.txt AC 377 ms 9364 KiB
058.txt AC 346 ms 9448 KiB
059.txt AC 390 ms 9368 KiB
060.txt AC 388 ms 9452 KiB
061.txt AC 388 ms 9428 KiB
062.txt AC 385 ms 9248 KiB
063.txt AC 384 ms 9252 KiB
064.txt AC 386 ms 9196 KiB
065.txt AC 390 ms 9344 KiB
066.txt AC 384 ms 9244 KiB
067.txt AC 385 ms 9384 KiB
068.txt AC 385 ms 9340 KiB
069.txt AC 390 ms 9384 KiB
070.txt AC 386 ms 9360 KiB
071.txt AC 389 ms 9340 KiB
072.txt AC 390 ms 9300 KiB
073.txt AC 386 ms 9452 KiB
074.txt AC 386 ms 9344 KiB
075.txt AC 387 ms 9364 KiB
076.txt AC 385 ms 9196 KiB
077.txt AC 384 ms 9360 KiB
078.txt AC 384 ms 9376 KiB
079.txt AC 392 ms 9228 KiB
080.txt AC 391 ms 9300 KiB
081.txt AC 387 ms 9380 KiB
082.txt AC 388 ms 9344 KiB
083.txt AC 388 ms 9364 KiB
084.txt AC 386 ms 9344 KiB
085.txt AC 384 ms 9428 KiB
086.txt AC 387 ms 9376 KiB
087.txt AC 386 ms 9240 KiB
088.txt AC 382 ms 9368 KiB
example0.txt AC 216 ms 9344 KiB
example1.txt AC 228 ms 9428 KiB