oj.uz

Submission #577864

# Submission time Handle Problem Language Result Execution time Memory
577864 2022-06-15T10:37:27 Z vanic Uplifting Excursion (BOI22_vault) C++14
0 / 100
 287 ms 500416 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <cstring>

using namespace std;

const int maxn=105, maxval=6e5;

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, 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

# Verdict Execution time Memory Grader output
1 Correct 90 ms 246852 KB Output is correct
2 Correct 90 ms 246828 KB Output is correct
3 Correct 88 ms 246772 KB Output is correct
4 Correct 88 ms 246792 KB Output is correct
5 Runtime error 287 ms 500416 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 246852 KB Output is correct
2 Correct 90 ms 246828 KB Output is correct
3 Correct 88 ms 246772 KB Output is correct
4 Correct 88 ms 246792 KB Output is correct
5 Runtime error 287 ms 500416 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 246792 KB Output is correct
2 Incorrect 91 ms 246764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 246792 KB Output is correct
2 Incorrect 91 ms 246764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 246792 KB Output is correct
2 Incorrect 91 ms 246764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 246852 KB Output is correct
2 Correct 90 ms 246828 KB Output is correct
3 Correct 88 ms 246772 KB Output is correct
4 Correct 88 ms 246792 KB Output is correct
5 Runtime error 287 ms 500416 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 246792 KB Output is correct
2 Incorrect 91 ms 246764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 246852 KB Output is correct
2 Correct 90 ms 246828 KB Output is correct
3 Correct 88 ms 246772 KB Output is correct
4 Correct 88 ms 246792 KB Output is correct
5 Runtime error 287 ms 500416 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 246792 KB Output is correct
2 Incorrect 91 ms 246764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 246852 KB Output is correct
2 Correct 90 ms 246828 KB Output is correct
3 Correct 88 ms 246772 KB Output is correct
4 Correct 88 ms 246792 KB Output is correct
5 Runtime error 287 ms 500416 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -