제출 #1071452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071452		zh_h	Snail (NOI18_snail)	C++17	37 / 100	1 ms	856 KiB

snail

#include <bits/stdc++.h>
#define lint long long
#define pb push_back
#define mp make_pair
using namespace std;
lint MOD = 1e9 + 7;
int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    lint height, n;
    cin >> height >> n;

    //* while taking the input, find:
    //* 1. the average move per day
    //* 2. the highest that you can reach per day

    vector<lint> p;
    lint ave=0, highest=0, lowest=0;
    lint count=0;
    for(lint i = 0; i < n; i ++){
        lint temp;
        cin >> temp;
        p.pb(temp);

        count += temp;
        // if(count < 0){count = 0;}
        highest = max(highest, count);
        lowest = min(lowest, count);

        ave += temp;
    }

    if(highest >= height){
        lint total = 0;
        for(lint i = 0; i < n; i ++){
            total += p[i];
            if(total < 0){total = 0;}
            if(total >= height){
                cout << 0 << " " << i;
                break;
            }
        }
    }
    else if(ave <= 0){
        lint counting = 0;
        for(int j = 0; j < 2; j ++){
            for(int i = 0; i < n; i ++){
                if(counting < 0){counting = 0;}
                counting += p[i];
                if(counting >= height){cout << j << " " << i; break;}
            }
            if(counting >= height){break;}
        }
        if(counting < height){cout << -1 << " " << -1;}
    }
    else{
        //* after N days
        //* at the N+1_th days, the snail reach the highest at some moment
        //* so basically, N*ave < height, N*ave + highest >= height
        //* search the N+1_th day

        //* first step: find smallest N such that N*ave >= height - highest
        //* can use binary search
        //* or just MATH

        //* so we need a new "highest" due to the technical issue...
        //* (for some reason but i lazy to explain why)
        highest = 0;
        lint counting = 0;
        for(int i = 0; i < n; i ++){
            counting += p[i];
            highest = max(highest, counting);
        }

        lint N;
        //*ceil((height - highest)/ave;
        N = (height - highest + ave - 1) / ave;
        
        lint total = N*ave;
        for(lint i = 0; i < n; i ++){
            total += p[i];
            if(total < 0){total = 0;}
            if(total >= height){
                cout << N << " " << i;
                break;
            }
        }
        
    }

    return 0;
}

// 5 -10 50 -100 300

// day 1: 300
// day 2: 

// 2 -10 8
// height = 10
// highest = 8
// ave = 0

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