Submission #1276191


Source Code Expand

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    vector<int> b(n);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    const long long int INF=1e15;
    vector<pair<long long int,long long int>> dp(n+1,{INF,-INF});
    dp[0]={0,0};
    int maxb=b[0];
    for(int i=1;i<=n;i++){
        if(dp[i-1].first>=n){
            break;
        }
        if(dp[i-1].second+a[i-1]>=0){
            dp[i]={dp[i-1].first+1,dp[i-1].second+a[i-1]};
        }
        else{
            int lack=-(dp[i-1].second+a[i-1]);
            if(maxb<=0){
                break;
            }
            int day=lack/maxb+(lack%maxb!=0);
            dp[i]={dp[i-1].first+1+day,dp[i-1].second+a[i-1]+day*maxb};
        }
        if(i==n) break;
        maxb=max(maxb,b[i]);
    }
    maxb=b[0];
    long long int res=0;
    for(int i=0;i<=n;i++){
        if(dp[i].first>n) break;    
        res=max(res,dp[i].second+(n-dp[i].first)*maxb);
        if(i>=n-1) continue;
        maxb=max(maxb,b[i+1]);
    }
    cout<<res<<endl;
    return 0;
}

Submission Info

Submission Time
Task D - 高橋君の旅行
User nikutto
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1142 Byte
Status AC
Exec Time 90 ms
Memory 2560 KB

Judge Result

Set Name Small All
Score / Max Score 3 / 3 197 / 197
Status
AC × 13
AC × 49
Set Name Test Cases
Small 00_small_sample_00.txt, 00_small_sample_01.txt, 00_small_sample_02.txt, 00_small_sample_03.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 90_small_teuchi_00.txt, 90_small_teuchi_01.txt, 90_small_teuchi_02.txt
All 00_small_sample_00.txt, 00_small_sample_01.txt, 00_small_sample_02.txt, 00_small_sample_03.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 20_large_01.txt, 20_large_02.txt, 20_large_03.txt, 20_large_04.txt, 20_large_05.txt, 20_large_06.txt, 20_large_07.txt, 20_large_08.txt, 20_large_09.txt, 20_large_10.txt, 20_large_11.txt, 20_large_12.txt, 20_large_13.txt, 20_large_14.txt, 20_large_15.txt, 20_large_16.txt, 20_large_17.txt, 20_large_18.txt, 20_large_19.txt, 20_large_20.txt, 20_large_21.txt, 20_large_22.txt, 20_large_23.txt, 20_large_24.txt, 20_large_25.txt, 20_large_26.txt, 20_large_27.txt, 20_large_28.txt, 20_large_29.txt, 20_large_30.txt, 30_run_through_01.txt, 70_maximum_01.txt, 80_hand_01.txt, 80_hand_02.txt, 80_hand_03.txt, 80_hand_04.txt, 90_small_teuchi_00.txt, 90_small_teuchi_01.txt, 90_small_teuchi_02.txt
Case Name Status Exec Time Memory
00_small_sample_00.txt AC 1 ms 256 KB
00_small_sample_01.txt AC 1 ms 256 KB
00_small_sample_02.txt AC 1 ms 256 KB
00_small_sample_03.txt AC 1 ms 256 KB
10_small_01.txt AC 1 ms 256 KB
10_small_02.txt AC 1 ms 256 KB
10_small_03.txt AC 1 ms 256 KB
10_small_04.txt AC 1 ms 256 KB
10_small_05.txt AC 1 ms 256 KB
10_small_06.txt AC 1 ms 256 KB
20_large_01.txt AC 72 ms 2560 KB
20_large_02.txt AC 84 ms 2560 KB
20_large_03.txt AC 85 ms 2560 KB
20_large_04.txt AC 72 ms 2560 KB
20_large_05.txt AC 85 ms 2560 KB
20_large_06.txt AC 85 ms 2560 KB
20_large_07.txt AC 72 ms 2560 KB
20_large_08.txt AC 90 ms 2560 KB
20_large_09.txt AC 84 ms 2560 KB
20_large_10.txt AC 71 ms 2560 KB
20_large_11.txt AC 83 ms 2560 KB
20_large_12.txt AC 83 ms 2560 KB
20_large_13.txt AC 61 ms 2560 KB
20_large_14.txt AC 72 ms 2560 KB
20_large_15.txt AC 75 ms 2560 KB
20_large_16.txt AC 60 ms 2560 KB
20_large_17.txt AC 71 ms 2560 KB
20_large_18.txt AC 71 ms 2560 KB
20_large_19.txt AC 69 ms 2560 KB
20_large_20.txt AC 81 ms 2560 KB
20_large_21.txt AC 81 ms 2560 KB
20_large_22.txt AC 58 ms 2560 KB
20_large_23.txt AC 69 ms 2560 KB
20_large_24.txt AC 69 ms 2560 KB
20_large_25.txt AC 69 ms 2560 KB
20_large_26.txt AC 81 ms 2560 KB
20_large_27.txt AC 81 ms 2560 KB
20_large_28.txt AC 70 ms 2560 KB
20_large_29.txt AC 81 ms 2560 KB
20_large_30.txt AC 81 ms 2560 KB
30_run_through_01.txt AC 78 ms 2560 KB
70_maximum_01.txt AC 87 ms 2560 KB
80_hand_01.txt AC 35 ms 2560 KB
80_hand_02.txt AC 34 ms 2560 KB
80_hand_03.txt AC 34 ms 2560 KB
80_hand_04.txt AC 33 ms 2560 KB
90_small_teuchi_00.txt AC 1 ms 256 KB
90_small_teuchi_01.txt AC 1 ms 256 KB
90_small_teuchi_02.txt AC 1 ms 256 KB