oj.uz

Submission #577866

# Submission time Handle Problem Language Result Execution time Memory
577866 2022-06-15T10:41:10 Z vanic Uplifting Excursion (BOI22_vault) C++14
0 / 100
 282 ms 500440 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){
	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);
	}
	if(l<0){
		l=-l;
		for(int i=0; i<n; i++){
			dodaj1(a[i], n-i);
		}
		for(int i=n+1; i<n*2+1; i++){
			dodaj2(a[i], i-n);
		}
	}
	else{
		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], n-i);
		}
	}
	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 96 ms 246816 KB Output is correct
2 Correct 94 ms 246876 KB Output is correct
3 Correct 87 ms 246828 KB Output is correct
4 Correct 91 ms 246868 KB Output is correct
5 Correct 105 ms 246768 KB Output is correct
6 Incorrect 96 ms 246856 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 246816 KB Output is correct
2 Correct 94 ms 246876 KB Output is correct
3 Correct 87 ms 246828 KB Output is correct
4 Correct 91 ms 246868 KB Output is correct
5 Correct 105 ms 246768 KB Output is correct
6 Incorrect 96 ms 246856 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 246848 KB Output is correct
2 Runtime error 282 ms 500440 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 246848 KB Output is correct
2 Runtime error 282 ms 500440 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 246848 KB Output is correct
2 Runtime error 282 ms 500440 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 246816 KB Output is correct
2 Correct 94 ms 246876 KB Output is correct
3 Correct 87 ms 246828 KB Output is correct
4 Correct 91 ms 246868 KB Output is correct
5 Correct 105 ms 246768 KB Output is correct
6 Incorrect 96 ms 246856 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 246848 KB Output is correct
2 Runtime error 282 ms 500440 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 246816 KB Output is correct
2 Correct 94 ms 246876 KB Output is correct
3 Correct 87 ms 246828 KB Output is correct
4 Correct 91 ms 246868 KB Output is correct
5 Correct 105 ms 246768 KB Output is correct
6 Incorrect 96 ms 246856 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 246848 KB Output is correct
2 Runtime error 282 ms 500440 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 246816 KB Output is correct
2 Correct 94 ms 246876 KB Output is correct
3 Correct 87 ms 246828 KB Output is correct
4 Correct 91 ms 246868 KB Output is correct
5 Correct 105 ms 246768 KB Output is correct
6 Incorrect 96 ms 246856 KB Output isn't correct
7 Halted 0 ms 0 KB -