Submission #676596

#	Time	Username	Problem	Language	Result	Execution time	Memory
676596		penguin133	Snail (NOI18_snail)	C++17	34 / 100	3 ms	468 KiB

snail

#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;
		int tmp = 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 (stderr)

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

• Subtask 1: 0 / 11
• Subtask 2: 9 / 9
• Subtask 3: 25 / 25
• Subtask 4: 0 / 17
• Subtask 5: 0 / 38