oj.uz

Submission #745232

# Submission time Handle Problem Language Result Execution time Memory
745232 2023-05-19T15:14:20 Z 박상훈(#9964) Uplifting Excursion (BOI22_vault) C++17
0 / 100
 690 ms 2764 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int SFT = 90090;
int n;
ll L, a[1010], b[1010];
bitset<180180> dp[2][606];

ll getmin(ll v, bool flag = 0){
	ll ret = 0;
	for (int i=-n;i<=n;i++){
		ret += (ll)i * min(v, a[i+n]);
		if (flag) b[i+n] = min(v, a[i+n]);
		v -= min(v, a[i+n]);
	}
	return ret;
}

ll getmax(ll v, bool flag = 0){
	ll ret = 0;
	for (int i=n;i>=-n;i--){
		ret += (ll)i * min(v, a[i+n]);
		if (flag) b[i+n] = min(v, a[i+n]);
		v -= min(v, a[i+n]);
	}
	return ret;
}

void NO(){
	printf("impossible\n");
	exit(0);
}

void solve(ll v){
	ll mn = getmin(v), mx = getmax(v);
	if (abs(mn-L) > n && abs(mx-L) > n) assert(0);
	if (abs(mn-L) <= n){
		reverse(a, a+n*2+1);
		L = -L;
		mn = getmin(v), mx = getmax(v);
		if (abs(mn-L) > n && abs(mx-L) > n) assert(0);
	}
	getmax(v, 1);

	int z = 0;
	ll r = n+2;
	
	//init
	dp[0][0][0+SFT] = 1;

	for (int i=n;i>=-n;i--){
		if (b[i+n] > 0){
			for (int j=1;j<=min(b[i+n], r/2);j++){
				z ^= 1;
				for (int p=-1;p<r;p++){
					
					if (p+1 < j) dp[z][p+1] = dp[z^1][p+1];
					else if (i>=0) dp[z][p+1] = dp[z^1][p+1] | (dp[z^1][p] << i);
					else dp[z][p+1] = dp[z^1][p+1] | (dp[z^1][p] >> (-i));
					
				}
			}
		}

		if (b[i+n] < a[i+n]){
			for (int j=1;j<=min(a[i+n]-b[i+n], r/2);j++){
				z ^= 1;
				for (int p=1;p<=r+1;p++){
					
					if (r-p+1 < j) dp[z][p-1] = dp[z^1][p-1];
					else if (i>=0) dp[z][p-1] = dp[z^1][p-1] | (dp[z^1][p] >> i);
					else dp[z][p-1] = dp[z^1][p-1] | (dp[z^1][p] << (-i));
					
				}
			}
		}
	}

	ll need = mx - L;
	for (int i=0;i<=r;i++) if (dp[z][i][need+SFT]){
		printf("%lld\n", v-i);
		return;
	}
	NO();
}

int main(){
	scanf("%d %lld", &n, &L);

	ll mS = 0, pS = 0, S = 0;
	for (int i=0;i<=n*2;i++){
		scanf("%lld", a+i);
		S += a[i];
		if (i-n < 0) mS += a[i];
		else if (i-n > 0) pS += a[i];
	} 

	// printf("%lld %lld %lld %lld\n", mS, pS, getmin(mS), getmax(pS));
	if (L < getmin(mS)) NO();
	if (L > getmax(pS)) NO();

	ll l = mS, r = S, vmn = mS;
	while(l<=r){
		ll mid = (l+r)/2;
		if (getmin(mid) <= L) vmn = mid, l = mid+1;
		else r = mid-1;
	}

	l = pS, r = S;
	ll vmx = pS;
	while(l<=r){
		ll mid = (l+r)/2;
		if (getmax(mid) >= L) vmx = mid, l = mid+1;
		else r = mid-1;
	}

	ll v = min(vmn, vmx); // [v+1, S]는 불가능
	// printf("%lld(%lld, %lld) -> %lld %lld\n", v, vmn, vmx, getmin(v), getmax(v));
	if (!(getmin(v) <= L) || !(getmax(v) >= L)) NO();
	solve(v);
}

Compilation message

vault.cpp: In function 'int main()':
vault.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d %lld", &n, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
vault.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%lld", a+i);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 552 ms 2764 KB Output is correct
7 Correct 235 ms 2644 KB Output is correct
8 Correct 551 ms 2740 KB Output is correct
9 Correct 690 ms 2736 KB Output is correct
10 Incorrect 19 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 552 ms 2764 KB Output is correct
7 Correct 235 ms 2644 KB Output is correct
8 Correct 551 ms 2740 KB Output is correct
9 Correct 690 ms 2736 KB Output is correct
10 Incorrect 19 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1000 KB Output is correct
2 Correct 75 ms 1748 KB Output is correct
3 Correct 23 ms 1872 KB Output is correct
4 Correct 79 ms 1876 KB Output is correct
5 Correct 103 ms 1748 KB Output is correct
6 Correct 77 ms 1796 KB Output is correct
7 Incorrect 12 ms 1876 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1000 KB Output is correct
2 Correct 75 ms 1748 KB Output is correct
3 Correct 23 ms 1872 KB Output is correct
4 Correct 79 ms 1876 KB Output is correct
5 Correct 103 ms 1748 KB Output is correct
6 Correct 77 ms 1796 KB Output is correct
7 Incorrect 12 ms 1876 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1000 KB Output is correct
2 Correct 75 ms 1748 KB Output is correct
3 Correct 23 ms 1872 KB Output is correct
4 Correct 79 ms 1876 KB Output is correct
5 Correct 103 ms 1748 KB Output is correct
6 Correct 77 ms 1796 KB Output is correct
7 Incorrect 12 ms 1876 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 552 ms 2764 KB Output is correct
7 Correct 235 ms 2644 KB Output is correct
8 Correct 551 ms 2740 KB Output is correct
9 Correct 690 ms 2736 KB Output is correct
10 Incorrect 19 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1000 KB Output is correct
2 Correct 75 ms 1748 KB Output is correct
3 Correct 23 ms 1872 KB Output is correct
4 Correct 79 ms 1876 KB Output is correct
5 Correct 103 ms 1748 KB Output is correct
6 Correct 77 ms 1796 KB Output is correct
7 Incorrect 12 ms 1876 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 552 ms 2764 KB Output is correct
7 Correct 235 ms 2644 KB Output is correct
8 Correct 551 ms 2740 KB Output is correct
9 Correct 690 ms 2736 KB Output is correct
10 Incorrect 19 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1000 KB Output is correct
2 Correct 75 ms 1748 KB Output is correct
3 Correct 23 ms 1872 KB Output is correct
4 Correct 79 ms 1876 KB Output is correct
5 Correct 103 ms 1748 KB Output is correct
6 Correct 77 ms 1796 KB Output is correct
7 Incorrect 12 ms 1876 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 552 ms 2764 KB Output is correct
7 Correct 235 ms 2644 KB Output is correct
8 Correct 551 ms 2740 KB Output is correct
9 Correct 690 ms 2736 KB Output is correct
10 Incorrect 19 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -