oj.uz

Submission #577871

# Submission time Handle Problem Language Result Execution time Memory
577871 2022-06-15T10:48:42 Z vanic Uplifting Excursion (BOI22_vault) C++14
0 / 100
 5000 ms 500400 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<maxval; 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<maxval; 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=maxval-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<maxval; 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));
	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);
	}
	dp[0][0]=a[n];
	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] << '\n';
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 246756 KB Output is correct
2 Correct 159 ms 246992 KB Output is correct
3 Correct 145 ms 246872 KB Output is correct
4 Correct 512 ms 246860 KB Output is correct
5 Execution timed out 5066 ms 246872 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 246756 KB Output is correct
2 Correct 159 ms 246992 KB Output is correct
3 Correct 145 ms 246872 KB Output is correct
4 Correct 512 ms 246860 KB Output is correct
5 Execution timed out 5066 ms 246872 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 246876 KB Output is correct
2 Runtime error 307 ms 500400 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 541 ms 246876 KB Output is correct
2 Runtime error 307 ms 500400 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 541 ms 246876 KB Output is correct
2 Runtime error 307 ms 500400 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 160 ms 246756 KB Output is correct
2 Correct 159 ms 246992 KB Output is correct
3 Correct 145 ms 246872 KB Output is correct
4 Correct 512 ms 246860 KB Output is correct
5 Execution timed out 5066 ms 246872 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 246876 KB Output is correct
2 Runtime error 307 ms 500400 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 160 ms 246756 KB Output is correct
2 Correct 159 ms 246992 KB Output is correct
3 Correct 145 ms 246872 KB Output is correct
4 Correct 512 ms 246860 KB Output is correct
5 Execution timed out 5066 ms 246872 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 246876 KB Output is correct
2 Runtime error 307 ms 500400 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 160 ms 246756 KB Output is correct
2 Correct 159 ms 246992 KB Output is correct
3 Correct 145 ms 246872 KB Output is correct
4 Correct 512 ms 246860 KB Output is correct
5 Execution timed out 5066 ms 246872 KB Time limit exceeded
6 Halted 0 ms 0 KB -