oj.uz

Submission #488491

# Submission time Handle Problem Language Result Execution time Memory
488491 2021-11-19T09:26:10 Z KienTran Snail (NOI18_snail) C++14
9 / 100
 2 ms 344 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int O = 2e5 + 5;
const int base = 15 + 5;

int n, h, Max, sum, pos, p[O];

void solban(){
    int res = 0, day = 0;
    for (;;){
        for (int i = 1; i <= n; ++ i){
            res += p[i];
            if (res >= h){
                cout << day << " " << i - 1 << endl;
                return;
            }
        }
        day += 1;
    }
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(0));
    cin >> h >> n;
    //h = rand() % base + 5;
    //n = rand() % base + 5;
    //cout << h << " " << n << endl;
    for (int i = 1; i <= n; ++ i){
        cin >> p[i];
        //p[i] = rand() % base + 5;
        //if (rand() & 1) p[i] = -p[i];
        //cout << p[i] << endl;
        sum += p[i];
        pos += p[i];
        pos = max(pos, 0ll);
        Max = max(Max, pos);
    }

    if (Max < h && sum <= 0) return cout << "-1 -1", 0;

    //solban();

    if (Max >= h){
        cout << 0 << " ";
        sum = 0;
        for (int i = 1; i <= n; ++ i){
            sum += p[i];
            sum = max(sum, 0ll);
            if (sum >= h){
                cout << i - 1;
                break;
            }
        }
        return 0;
    }

    int l = 0, r = 1e12;
    while (l <= r){
        int mid = (l + r) / 2;
        /// bo len duoc vao ngay mid
        if (max(0ll, (mid - 1)) * sum + Max >= h) r = mid - 1;
        else l = mid + 1;
    }

    r = max(0ll, r);
    cout << r << " ";
    sum *= r;

    for (int i = 1; i <= n; ++ i){
        sum += p[i];
        if (sum >= h) return cout << i - 1, 0;
    }
}
/***
9 12
8
7
-13
7
9
-6
-12
-10
-6
-7
-12
-11
***/

Compilation message

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

Subtask #1
0 / 11.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 272 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 1 ms 344 KB Output isn't correct

Subtask #5
0 / 38.0

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