oj.uz

Submission #676596

# Submission time Handle Problem Language Result Execution time Memory
676596 2022-12-31T11:43:52 Z penguin133 Snail (NOI18_snail) C++17
34 / 100
 3 ms 468 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;
		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

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Incorrect 2 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -