京都大学プログラミングコンテスト2015

Submission #1276191

Source codeソースコード

#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

Task問題 D - 高橋君の旅行
User nameユーザ名 nikutto
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 200
Source lengthソースコード長 1142 Byte
File nameファイル名
Exec time実行時間 90 ms
Memory usageメモリ使用量 2560 KB

Test case

Set

Set name Score得点 / Max score Cases
Small 3 / 3 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 197 / 197 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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