oj.uz

Submission #745181

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

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

// struct BITSET{
// 	unsigned long long bt[MX+1]; //bt[sz] should be 0
// 	int sz; //size < MX
// }dp[2][606];

// void _bit_on(BITSET &B, int pos){
// 	if ((pos>>6) >= sz){
// 		for (int i=sz+1;i<=(pos>>6)+1;i++) bt[i] = 0;
// 		sz = (pos>>6)+1;
// 	}
// 	B.bt[pos>>6] |= 1LL<<(pos&63);
// }

// bool _chk_on(BITSET &B, int pos){
// 	return ((pos>>6) < sz) && (B.bt[pos>>6] & (1LL<<(pos&63)));
// }

// void _shift_or(BITSET &prv, BITSET &now, int sft){
// 	now.sz = prv.sz;
// 	for (int i=0;i<=sz;i++) now.bt[i] = prv.bt[i];


// }

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);
	}
	else getmax(v, 1);

	int z = 0;
	ll r = n*2+2;
	
	//init
	// _bit_on(dp[0][0], 0);
	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);j++){
				z ^= 1;
				dp[z][0] = dp[z^1][0];
				for (int p=0;p<r;p++){
					// _shift_or(dp[z^1][p], dp[z][p+1], i);
					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));
					// printf("i = %d, j = %d, p+1 = %d -> ", i, j, p+1);
					// for (int x=-20;x<20;x++){
					// 	if (x==0) printf(" ");
					// 	printf("%d", (int)dp[z][p+1][x+SFT]);
					// } 
					// printf("\n");
				}
			}
		}

		if (b[i+n] < a[i+n]){
			for (int j=1;j<=min(a[i+n]-b[i+n], r);j++){
				z ^= 1;
				dp[z][r] = dp[z^1][r];
				for (int p=1;p<=r;p++){
					// _shift_or(dp[z^1][p], dp[z][p-1], -i);
					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));
					// printf("i = %d, j = %d, p-1 = %d -> ", i, j, p-1);
					// for (int x=-20;x<20;x++){
					// 	if (x==0) printf(" ");
					// 	printf("%d", (int)dp[z][p-1][x+SFT]);
					// } 
					// printf("\n");
				}
			}
		}
	}

	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:124:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  scanf("%d %lld", &n, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
vault.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |   scanf("%lld", a+i);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 246 ms 820 KB Output is correct
7 Correct 97 ms 812 KB Output is correct
8 Incorrect 219 ms 816 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 246 ms 820 KB Output is correct
7 Correct 97 ms 812 KB Output is correct
8 Incorrect 219 ms 816 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Incorrect 52 ms 596 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 2 ms 340 KB Output is correct
2 Incorrect 52 ms 596 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 2 ms 340 KB Output is correct
2 Incorrect 52 ms 596 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 246 ms 820 KB Output is correct
7 Correct 97 ms 812 KB Output is correct
8 Incorrect 219 ms 816 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Incorrect 52 ms 596 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 246 ms 820 KB Output is correct
7 Correct 97 ms 812 KB Output is correct
8 Incorrect 219 ms 816 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Incorrect 52 ms 596 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 246 ms 820 KB Output is correct
7 Correct 97 ms 812 KB Output is correct
8 Incorrect 219 ms 816 KB Output isn't correct
9 Halted 0 ms 0 KB -