oj.uz

Submission #677222

# Submission time Handle Problem Language Result Execution time Memory
677222 2023-01-02T15:09:00 Z dsyz Solar Storm (NOI20_solarstorm) C++17
18 / 100
 470 ms 221432 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
vector<ll> v[MAXN];
int parent[20][MAXN]; //(2^19 + 2^18 + 2^17 ... + 2^0) = (2^20 - 1) which is > 10^6
bool visited[MAXN];
void dfs(ll x){
	visited[x] = 1;
	for(auto u : v[x]){
		if(!visited[u]){
			parent[0][u] = x;
			visited[u] = 1;
			dfs(u);
		}
	}
}
ll fp(ll x,ll k){
	for(ll i = 19;i >= 0;i--){
		if(k >= (1<<i)){
			if(x == -1) return -1;
			x = parent[i][x];
			k -= (1<<i);
		}
	}
	return x;
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,S,K;
	cin>>N>>S>>K;
	ll d[N];
	ll arr[N];
	memset(d,0,sizeof(d));
	for(ll i = 1;i < N;i++){
		ll a;
		cin>>a;
		d[i] = d[i - 1] + a;
	}
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
	}
	ll indeg[N];
	memset(indeg,0,sizeof(indeg));
	for(ll i = 0;i < N;i++){
		ll p = lower_bound(d,d + N,d[i] - K) - d - 1;
		if(p < 0 || p == i) continue;
		p = lower_bound(d,d + N,d[p] - K) - d;
		if(p < 0 || p == i) continue;
		v[p].push_back(i);
		indeg[i]++;
	}
	memset(visited,0,sizeof(visited));
	memset(parent,-1,sizeof(parent));
	for(ll i = 0;i < N;i++){
		if(indeg[i] == 0){
			visited[i] = 1;
			parent[0][i] = -1;
			dfs(i);
		}
	}
	for(ll k = 1;k < 20;k++){
		for(ll i = 0;i < N;i++){
			if(parent[k - 1][i] != -1){
				parent[k][i] = parent[k - 1][parent[k - 1][i]];
			}else{
				parent[k][i] = -1;
			}
		}
	}
	ll psum[N];
	ll cur = 0;
	for(ll i = 0;i < N;i++){
		cur += arr[i];
		psum[i] = cur;
	}
	ll usedshields = 1;
	ll E = upper_bound(d,d + N,K) - d - 1;
	ll modulepos = d[E];
	for(ll i = E + 1;i < N && usedshields <= S;i++){
		E++;
		if(d[i] > modulepos + K || i == N - 1){
			usedshields++;
			modulepos = d[i];
		}
		if(usedshields > S) E--;
	}
	ll ans = psum[E];
	pair<ll,ll> range = {0,E};
	for(ll r = E + 1;r < N;r++){
		ll l = fp(r,S - 1);
		if(l == -1) l = r;
		ll s = lower_bound(d,d + N,d[l] - K) - d;
		ll e = upper_bound(d,d + N,d[r] + K) - d - 1;
		ll sum = psum[e];
		if(s >= 1) sum -= psum[s - 1];
		if(sum > ans){
			range = {s,e};
			ans = sum;
		}
	}
	vector<ll> modules;
	E = upper_bound(d,d + N,d[range.first] + K) - d - 1;
	modules.push_back(E + 1);
	modulepos = d[E];
	for(ll i = E + 1;i <= range.second;i++){
		E++;
		if(d[i] > modulepos + K){
			modules.push_back(i + 1);
			modulepos = d[i];
		}
	}
	cout<<modules.size()<<'\n';
	for(auto u : modules){
		cout<<u<<" ";
	}
	cout<<'\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 102988 KB Output is correct
2 Correct 44 ms 104028 KB Output is correct
3 Correct 47 ms 104140 KB Output is correct
4 Correct 45 ms 103412 KB Output is correct
5 Correct 40 ms 103036 KB Output is correct
6 Correct 43 ms 103356 KB Output is correct
7 Correct 41 ms 103372 KB Output is correct
8 Correct 43 ms 103372 KB Output is correct
9 Correct 46 ms 103496 KB Output is correct
10 Correct 45 ms 103732 KB Output is correct
11 Correct 44 ms 103628 KB Output is correct
12 Correct 43 ms 103472 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 137308 KB Output is correct
2 Incorrect 169 ms 129576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 102988 KB Output is correct
2 Correct 44 ms 104028 KB Output is correct
3 Correct 47 ms 104140 KB Output is correct
4 Correct 45 ms 103412 KB Output is correct
5 Correct 40 ms 103036 KB Output is correct
6 Correct 43 ms 103356 KB Output is correct
7 Correct 41 ms 103372 KB Output is correct
8 Correct 43 ms 103372 KB Output is correct
9 Correct 46 ms 103496 KB Output is correct
10 Correct 45 ms 103732 KB Output is correct
11 Correct 44 ms 103628 KB Output is correct
12 Correct 43 ms 103472 KB Output is correct
13 Correct 199 ms 137308 KB Output is correct
14 Incorrect 169 ms 129576 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 200464 KB Output is correct
2 Correct 269 ms 159092 KB Output is correct
3 Correct 301 ms 163116 KB Output is correct
4 Correct 412 ms 190088 KB Output is correct
5 Correct 366 ms 187360 KB Output is correct
6 Correct 393 ms 192460 KB Output is correct
7 Correct 470 ms 221432 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 102988 KB Output is correct
2 Correct 44 ms 104028 KB Output is correct
3 Correct 47 ms 104140 KB Output is correct
4 Correct 45 ms 103412 KB Output is correct
5 Correct 40 ms 103036 KB Output is correct
6 Correct 43 ms 103356 KB Output is correct
7 Correct 41 ms 103372 KB Output is correct
8 Correct 43 ms 103372 KB Output is correct
9 Correct 46 ms 103496 KB Output is correct
10 Correct 45 ms 103732 KB Output is correct
11 Correct 44 ms 103628 KB Output is correct
12 Correct 43 ms 103472 KB Output is correct
13 Correct 48 ms 103448 KB Output is correct
14 Incorrect 46 ms 103684 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 102988 KB Output is correct
2 Correct 44 ms 104028 KB Output is correct
3 Correct 47 ms 104140 KB Output is correct
4 Correct 45 ms 103412 KB Output is correct
5 Correct 40 ms 103036 KB Output is correct
6 Correct 43 ms 103356 KB Output is correct
7 Correct 41 ms 103372 KB Output is correct
8 Correct 43 ms 103372 KB Output is correct
9 Correct 46 ms 103496 KB Output is correct
10 Correct 45 ms 103732 KB Output is correct
11 Correct 44 ms 103628 KB Output is correct
12 Correct 43 ms 103472 KB Output is correct
13 Correct 199 ms 137308 KB Output is correct
14 Incorrect 169 ms 129576 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 102988 KB Output is correct
2 Correct 44 ms 104028 KB Output is correct
3 Correct 47 ms 104140 KB Output is correct
4 Correct 45 ms 103412 KB Output is correct
5 Correct 40 ms 103036 KB Output is correct
6 Correct 43 ms 103356 KB Output is correct
7 Correct 41 ms 103372 KB Output is correct
8 Correct 43 ms 103372 KB Output is correct
9 Correct 46 ms 103496 KB Output is correct
10 Correct 45 ms 103732 KB Output is correct
11 Correct 44 ms 103628 KB Output is correct
12 Correct 43 ms 103472 KB Output is correct
13 Correct 199 ms 137308 KB Output is correct
14 Incorrect 169 ms 129576 KB Output isn't correct
15 Halted 0 ms 0 KB -