oj.uz

답안 #577865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577865 2022-06-15T10:39:13 Z vanic Uplifting Excursion (BOI22_vault) C++14
0 / 100
 298 ms 500408 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <cstring>

using namespace std;

const int maxn=105, maxval=6e5;
typedef long long ll;

int a[maxn*2];
int dp[maxval][maxn];

void dodaj1(int br, int x){
	for(int i=x; i<maxn; i++){
		for(int j=1; j<=br; j++){
			if(dp[i-x][j-1]!=-1){
				dp[i][j]=dp[i-x][j-1]+1;
			}
		}
	}
	for(int i=0; i<maxn; i++){
		int maksi=-1;
		for(int j=0; j<=br; j++){
			maksi=max(maksi, dp[i][j]);
			dp[i][j]=-1;
		}
		dp[i][0]=maksi;
	}
}

void dodaj2(int br, int x){
	x=-x;
	for(int i=maxn-x-1; i>=0; i--){
		for(int j=1; j<=br; j++){
			if(dp[i+x][j-1]!=-1){
				dp[i][j]=dp[i+x][j-1]+1;
			}
		}
	}
	for(int i=0; i<maxn; i++){
		int maksi=-1;
		for(int j=0; j<=br; j++){
			maksi=max(maksi, dp[i][j]);
			dp[i][j]=-1;
		}
		dp[i][0]=maksi;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(dp, -1, sizeof(dp));
	dp[0][0]=0;
	int n;
	ll l;
	cin >> n >> l;
	assert(n<maxn);
	for(int i=0; i<n*2+1; i++){
		cin >> a[i];
		assert(a[i]<maxn);
	}
	for(int i=n+1; i<n*2+1; i++){
		dodaj1(a[i], i-n);
	}
	for(int i=0; i<n; i++){
		dodaj2(a[i], i-n);
	}
	if(l>=maxval || dp[l][0]==-1){
		cout << "impossible\n";
	}
	else{
		cout <<  dp[l][0]+a[n] << '\n';
	}
	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 246788 KB Output is correct
2 Correct 107 ms 246772 KB Output is correct
3 Correct 99 ms 246860 KB Output is correct
4 Correct 88 ms 246860 KB Output is correct
5 Runtime error 298 ms 500408 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 246788 KB Output is correct
2 Correct 107 ms 246772 KB Output is correct
3 Correct 99 ms 246860 KB Output is correct
4 Correct 88 ms 246860 KB Output is correct
5 Runtime error 298 ms 500408 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 246836 KB Output is correct
2 Runtime error 290 ms 500340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 246836 KB Output is correct
2 Runtime error 290 ms 500340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 246836 KB Output is correct
2 Runtime error 290 ms 500340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 246788 KB Output is correct
2 Correct 107 ms 246772 KB Output is correct
3 Correct 99 ms 246860 KB Output is correct
4 Correct 88 ms 246860 KB Output is correct
5 Runtime error 298 ms 500408 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 246836 KB Output is correct
2 Runtime error 290 ms 500340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 246788 KB Output is correct
2 Correct 107 ms 246772 KB Output is correct
3 Correct 99 ms 246860 KB Output is correct
4 Correct 88 ms 246860 KB Output is correct
5 Runtime error 298 ms 500408 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 246836 KB Output is correct
2 Runtime error 290 ms 500340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 246788 KB Output is correct
2 Correct 107 ms 246772 KB Output is correct
3 Correct 99 ms 246860 KB Output is correct
4 Correct 88 ms 246860 KB Output is correct
5 Runtime error 298 ms 500408 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -