oj.uz

Submission #677562

# Submission time Handle Problem Language Result Execution time Memory
677562 2023-01-03T16:14:05 Z penguin133 Solar Storm (NOI20_solarstorm) C++17
18 / 100
 364 ms 200720 KB 
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
 
int n, s, k, A[1000005], B[1000005];
long long P[1000005], X[1000005];
pi pre[1000005];
int par[20][1000005];
vector<int> v[1000005];
bool vis[1000005];
void dfs(int x, int p){
	if(vis[x])return;
	vis[x] = 1;
	par[0][x] = p;
	for(auto i : v[x])dfs(i, x);
}
 
void solve(){
	cin >> n >> s >> k;
	for(int i=2;i<=n;i++)cin >> A[i], P[i] = P[i-1] + A[i];
	for(int i=1;i<=n;i++)cin >> B[i], X[i] = X[i-1] + B[i];
	for(int i=1;i<=n;i++){
		int lo = 1, hi = i, ans = hi;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(P[i] - P[mid] <= k)ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		lo = 1, hi = ans;
		int ans2 = ans;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(P[ans] - P[mid] <= k)ans2 = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		v[ans2-1].push_back(i);
		pre[i] = {ans2 - 1, ans};
	}
	for(int i=0;i<n;i++)dfs(i, 0);
	for(int i=1;i<=19;i++)for(int j=1;j<=n;j++)par[i][j] = par[i-1][par[i-1][j]];
	int in = 0;
  long long mx = 0;
	for(int i=1;i<=n;i++){
		int tmp = i;
		for(int j=19;j>=0;j--){
			if(s >> j & 1)tmp = par[j][tmp];
			if(tmp == 0)break;
		}
		if(X[i] - X[tmp] > mx)mx = X[i] - X[tmp], in = i;
	}
	int bt = in, rem = s;
	vector<int> ans;
	while(rem && bt){
		rem--;
		ans.push_back(pre[bt].se);
		bt = pre[bt].fi;
	}
	//cout << mx << '\n';
	cout << (int)ans.size() << '\n';
	for(auto i : ans)cout << i << " ";
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

SolarStorm.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 14 ms 25556 KB Output is correct
3 Correct 15 ms 25684 KB Output is correct
4 Correct 13 ms 24724 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 15 ms 24984 KB Output is correct
7 Correct 17 ms 25112 KB Output is correct
8 Correct 16 ms 25288 KB Output is correct
9 Correct 15 ms 24844 KB Output is correct
10 Correct 16 ms 25380 KB Output is correct
11 Correct 17 ms 25300 KB Output is correct
12 Correct 14 ms 24788 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 115508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 14 ms 25556 KB Output is correct
3 Correct 15 ms 25684 KB Output is correct
4 Correct 13 ms 24724 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 15 ms 24984 KB Output is correct
7 Correct 17 ms 25112 KB Output is correct
8 Correct 16 ms 25288 KB Output is correct
9 Correct 15 ms 24844 KB Output is correct
10 Correct 16 ms 25380 KB Output is correct
11 Correct 17 ms 25300 KB Output is correct
12 Correct 14 ms 24788 KB Output is correct
13 Incorrect 113 ms 115508 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 164264 KB Output is correct
2 Correct 151 ms 108876 KB Output is correct
3 Correct 164 ms 115148 KB Output is correct
4 Correct 247 ms 155728 KB Output is correct
5 Correct 227 ms 151804 KB Output is correct
6 Correct 253 ms 159324 KB Output is correct
7 Correct 364 ms 200720 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 14 ms 25556 KB Output is correct
3 Correct 15 ms 25684 KB Output is correct
4 Correct 13 ms 24724 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 15 ms 24984 KB Output is correct
7 Correct 17 ms 25112 KB Output is correct
8 Correct 16 ms 25288 KB Output is correct
9 Correct 15 ms 24844 KB Output is correct
10 Correct 16 ms 25380 KB Output is correct
11 Correct 17 ms 25300 KB Output is correct
12 Correct 14 ms 24788 KB Output is correct
13 Incorrect 15 ms 25172 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 14 ms 25556 KB Output is correct
3 Correct 15 ms 25684 KB Output is correct
4 Correct 13 ms 24724 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 15 ms 24984 KB Output is correct
7 Correct 17 ms 25112 KB Output is correct
8 Correct 16 ms 25288 KB Output is correct
9 Correct 15 ms 24844 KB Output is correct
10 Correct 16 ms 25380 KB Output is correct
11 Correct 17 ms 25300 KB Output is correct
12 Correct 14 ms 24788 KB Output is correct
13 Incorrect 113 ms 115508 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 14 ms 25556 KB Output is correct
3 Correct 15 ms 25684 KB Output is correct
4 Correct 13 ms 24724 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 15 ms 24984 KB Output is correct
7 Correct 17 ms 25112 KB Output is correct
8 Correct 16 ms 25288 KB Output is correct
9 Correct 15 ms 24844 KB Output is correct
10 Correct 16 ms 25380 KB Output is correct
11 Correct 17 ms 25300 KB Output is correct
12 Correct 14 ms 24788 KB Output is correct
13 Incorrect 113 ms 115508 KB Output isn't correct
14 Halted 0 ms 0 KB -