oj.uz

답안 #676597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676597 2022-12-31T11:44:43 Z penguin133 Snail (NOI18_snail) C++17
100 / 100
 2 ms 488 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
#define getchar_unlocked _getchar_nolock

int n, h, A[10005];
int cur = 0, rnd = 0, mx, sm;
void solve(){
	cin >> h >> n;
	for(int i=1;i<=n;i++)cin >> A[i], sm += A[i];
	mx = n;
	for(rnd=0;rnd<=n;){
		int mx2 = 0;
		for(int i=1;i<=n;i++){
			cur += A[i];
			if(cur >= h){
				cout << rnd << " " << i - 1;
				return;
			}
			if(cur <= 0)cur = 0, mx2 = i;
		}
		if(mx2 >= mx){
			cout << -1 << " " << -1;
			return;
		}
		rnd++;
		if(mx2 == 0)break;
		mx = mx2;
	}
	int l = 0, r = 1e12, ans = r + 1;
	while(l <= r){
		int m = (l + r) >> 1;
		__int128 tmp = (__int128)sm * m + cur;
		bool can = 0;
		if(tmp >= h)can = 1;
		for(int i=1;i<=n;i++){
			tmp += A[i];
			if(tmp >= h)can = 1;
		}
		if(can)ans = m, r = m - 1;
		else l = m + 1;
	}
	cout << rnd + ans << " ";
	int tmp = cur + ans * sm;
	for(int i=1;i<=n;i++){
		tmp += A[i];
		if(tmp >= h){
			cout << i - 1;
			return;
		}
	}
	assert(1 == 0);
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	while(tc--){
		solve();
	}
}

Compilation message

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

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 332 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 2 ms 488 KB Output is correct

Subtask #5
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 476 KB Output is correct
25 Correct 2 ms 424 KB Output is correct
26 Correct 2 ms 488 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 472 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct