oj.uz

답안 #677353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677353 2023-01-03T04:32:46 Z penguin133 Solar Storm (NOI20_solarstorm) C++17
28 / 100
 241 ms 262144 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], P[1000005], X[1000005];

void solve(){
	cin >> n >> s >> k;
	int dp[n+1][s+1] = {0};
	pi pre[n+1][s+1];
	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<=s;i++)dp[0][i] = 0;
	for(int i=1;i<=n;i++)dp[i][0] = 0;
	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;
		}
		for(int j=1;j<=s;j++){
			dp[i][j] = dp[i][j-1], pre[i][j] = {i, i};
			if(dp[ans2-1][j-1] + X[i] - X[ans2-1] > dp[i][j])dp[i][j] = dp[ans2-1][j-1] + X[i] - X[ans2-1], pre[i][j] = {ans2-1, ans};
			//cout << dp[i][j] << " ";
		}
		//cout << '\n';
	}
	int in = 0, mx = 0;
	for(int i=1;i<=n;i++)if(dp[i][s] > mx)mx = dp[i][s], in = i;
	//cout << mx << " " << in << '\n';
	pi bt = pre[in][s];
	int lol = s;
	cout << s << '\n';
	while(lol){
		cout << bt.se << ' ';
		bt = pre[bt.fi][--lol];
	}
}

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:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 1240 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 1 ms 596 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 72428 KB Output is correct
2 Correct 113 ms 47588 KB Output is correct
3 Correct 128 ms 48900 KB Output is correct
4 Correct 152 ms 52968 KB Output is correct
5 Correct 150 ms 61692 KB Output is correct
6 Correct 205 ms 81228 KB Output is correct
7 Correct 142 ms 54716 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 1240 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 165 ms 72428 KB Output is correct
14 Correct 113 ms 47588 KB Output is correct
15 Correct 128 ms 48900 KB Output is correct
16 Correct 152 ms 52968 KB Output is correct
17 Correct 150 ms 61692 KB Output is correct
18 Correct 205 ms 81228 KB Output is correct
19 Correct 142 ms 54716 KB Output is correct
20 Correct 119 ms 45776 KB Output is correct
21 Correct 172 ms 55384 KB Output is correct
22 Correct 180 ms 65024 KB Output is correct
23 Correct 155 ms 66696 KB Output is correct
24 Correct 165 ms 60716 KB Output is correct
25 Correct 204 ms 60764 KB Output is correct
26 Correct 145 ms 45864 KB Output is correct
27 Correct 184 ms 58432 KB Output is correct
28 Correct 191 ms 57716 KB Output is correct
29 Correct 241 ms 73888 KB Output is correct
30 Correct 176 ms 60748 KB Output is correct
31 Correct 172 ms 53460 KB Output is correct

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 106 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 1240 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Incorrect 149 ms 239416 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 1240 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 165 ms 72428 KB Output is correct
14 Correct 113 ms 47588 KB Output is correct
15 Correct 128 ms 48900 KB Output is correct
16 Correct 152 ms 52968 KB Output is correct
17 Correct 150 ms 61692 KB Output is correct
18 Correct 205 ms 81228 KB Output is correct
19 Correct 142 ms 54716 KB Output is correct
20 Correct 119 ms 45776 KB Output is correct
21 Correct 172 ms 55384 KB Output is correct
22 Correct 180 ms 65024 KB Output is correct
23 Correct 155 ms 66696 KB Output is correct
24 Correct 165 ms 60716 KB Output is correct
25 Correct 204 ms 60764 KB Output is correct
26 Correct 145 ms 45864 KB Output is correct
27 Correct 184 ms 58432 KB Output is correct
28 Correct 191 ms 57716 KB Output is correct
29 Correct 241 ms 73888 KB Output is correct
30 Correct 176 ms 60748 KB Output is correct
31 Correct 172 ms 53460 KB Output is correct
32 Runtime error 126 ms 262144 KB Execution killed with signal 9
33 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 1240 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 165 ms 72428 KB Output is correct
14 Correct 113 ms 47588 KB Output is correct
15 Correct 128 ms 48900 KB Output is correct
16 Correct 152 ms 52968 KB Output is correct
17 Correct 150 ms 61692 KB Output is correct
18 Correct 205 ms 81228 KB Output is correct
19 Correct 142 ms 54716 KB Output is correct
20 Correct 119 ms 45776 KB Output is correct
21 Correct 172 ms 55384 KB Output is correct
22 Correct 180 ms 65024 KB Output is correct
23 Correct 155 ms 66696 KB Output is correct
24 Correct 165 ms 60716 KB Output is correct
25 Correct 204 ms 60764 KB Output is correct
26 Correct 145 ms 45864 KB Output is correct
27 Correct 184 ms 58432 KB Output is correct
28 Correct 191 ms 57716 KB Output is correct
29 Correct 241 ms 73888 KB Output is correct
30 Correct 176 ms 60748 KB Output is correct
31 Correct 172 ms 53460 KB Output is correct
32 Runtime error 106 ms 262144 KB Execution killed with signal 9
33 Halted 0 ms 0 KB -