254962026-02-20 12:18:50PajerLeviSzitakötő (50 pont)cpp17Wrong answer 4/5057ms1592 KiB
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, k; cin >> n >> k;
	vector<int> w_og(n); for(int& x : w_og) cin >> x;
	int ans=0;
	// a k-adik fixinfo balra megy, mert tole jobbra a nagyobbak felfaljak
	
	// ha 0<m<k elindul jobbra, akk merge, kulonben tovabb
	
	// igazabol a balra meno larvak felfaljak a tole balra levo, jobbra meno larvakat, igy csak ok maradnak
	// J J B B J B J B B
	// B B   B   B B
	
	// innen meg bele lehetNE bonyolodni a dolgokba, de igazabol csak annyi a lenyeg, hogy a vegleges larva az a larvak osszege
	
	// ezt azert tehetjuk meg, mert tole jobbra levo larva "nem nyulhat bele" ebbe az intervallumba, igy effektive csak az az 1 osszeglarva letezik,
	// az eltolast viszont ki kell szamolni
	
	// tehat ez tortenik i<k-ra
	// de igazabol minket csak Rozsabimbo erdekel, ha el, akkor oszerinte haladunk, ha felfaljak, akkor vege
	
	// szoval csak azt kell kiszamolni, hogy a larvamasszivum az erosebb-e, mint Rozsabimbo
	// ez trivi., hiszen a larvamasszivum ereje a larvak osszege tole balra, addig, amig nem jobbra eszik
	// TEHAT akkor csak az a lenyeges, hogy tole kozvetlen balra meddig mennek jobbra a larvak, tobbi elhanyagolhato a bal oldalon
	
	// igy megvan a bal oldaltol fuggo lehetosegek szama
	
	// jobb oldal:
	// alapeset: mindenki B: w_og[m]<pref[m]-n | k<=m<=n mulik hogy eljen Rozsabimbo
	// van J: a tole jobbra levo bal felfalja
	// igy csak a balra menok maradnak, a kovetkezo balra levoig adodnak ossze az erok
	// J J B B J B J B B
	// B B   B   B B
	// igazabol az mindig marad, hogy milyen sulyokat (prefix) vesz fel, csak az nem, hogy melyeket hagyja ki
	// 1 2 3 4 5 6 7 8 9
	// 3 4   6   8 9
	// tehat minden prefixre tudni kell, meddig tud menni, es addig mindegy, ki merre megy
	
	#define MOD 1000000007
	vector<int> pow2(n+2, 1);
	for(int i=1;i<=n+1;i++) pow2[i]=(2*pow2[i-1])%MOD;
	
	vector<int> pref(n+1); for(int i=0;i<n;i++) pref[i+1]=pref[i]+w_og[i];
	int bal=1;
	k--;
	{
		int rozsabimboW=w_og[k];
		for(int i=k-1;0<=i;i--){
			// elso a jobb-blokk utan fix bal
			if(pref[i+1]<=rozsabimboW) bal=(bal+pow2[i])%MOD;
			rozsabimboW+=w_og[i];
		}
	}
	int jobb=0;
	for(int i=n;k<i;i--){
		// elso pref[i]: kivonja az intervallum elejet 0-(i-1)-ig
		// masodik pref[i]: Rozsabimbo ereje
		int lim=lower_bound(pref.begin()+i+1, pref.end(), pref[i]+pref[i])-pref.begin();
		if(i+1<lim) jobb=(jobb+pow2[lim-(i+1)])%MOD;
	}
	cout << (bal*(long long)(jobb))%MOD;
	
	/*for(int bm=0;bm<(1<<n);bm++){
		//printf("{%X %x}", bm, 0b1010);
		vector<array<int, 3>> pq;
		vector<bool> eaten(n, false);
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				int dirI=(bm>>i)&1, dirJ=(bm>>j)&1;
				if(dirI==1 && dirJ==0) pq.push_back({j-i, i, j});
				if(dirI==1 && dirJ==1) pq.push_back({2*(n-j)+j-i, i, j});
				if(dirI==0 && dirJ==0) pq.push_back({2*(i+1)+j-i, i, j});
				if(dirI==0 && dirJ==1) pq.push_back({2*(n+1)+j-i, i, j});
			}
		}
		sort(pq.begin(), pq.end());
		vector<int> w=w_og;
		for(auto [x, a, b] : pq){
			if(!eaten[a] && !eaten[b]){
				//printf("[%d %d %d]", x, a, b);
				if(w[a]<w[b]){
					eaten[a]=true;
					w[b]+=w[a];
				}
				else if(w[b]<w[a]){
					eaten[b]=true;
					w[a]+=w[b];
				}
				else if(a<b){
					eaten[a]=true;
					w[b]+=w[a];
				}
				else{
					eaten[b]=true;
					w[a]+=w[b];
				}
			}
		}
		//printf("\n");
		ans+=!eaten[k-1];
	}
	printf("%d", ans);*/
	return 0;
}
SubtaskSumTestVerdictTimeMemory
base4/50
1Accepted0/01ms316 KiB
2Wrong answer0/057ms1588 KiB
3Wrong answer0/11ms316 KiB
4Accepted1/11ms316 KiB
5Accepted1/11ms508 KiB
6Wrong answer0/11ms316 KiB
7Wrong answer0/11ms316 KiB
8Wrong answer0/11ms316 KiB
9Wrong answer0/11ms316 KiB
10Wrong answer0/21ms316 KiB
11Wrong answer0/21ms316 KiB
12Accepted2/21ms316 KiB
13Wrong answer0/21ms316 KiB
14Wrong answer0/21ms512 KiB
15Wrong answer0/21ms348 KiB
16Wrong answer0/21ms316 KiB
17Wrong answer0/21ms508 KiB
18Wrong answer0/21ms316 KiB
19Wrong answer0/22ms316 KiB
20Wrong answer0/21ms508 KiB
21Wrong answer0/11ms508 KiB
22Wrong answer0/237ms1568 KiB
23Wrong answer0/239ms1572 KiB
24Wrong answer0/257ms1572 KiB
25Wrong answer0/252ms1580 KiB
26Wrong answer0/252ms1584 KiB
27Wrong answer0/225ms1592 KiB
28Wrong answer0/241ms1332 KiB
29Wrong answer0/235ms1588 KiB
30Wrong answer0/257ms1332 KiB
31Wrong answer0/245ms1332 KiB