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

Submission #1275929

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    cin>>n;
    vector<long long int> a(n),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>> reach(n+1,{INF,-INF});
    reach[0]={0,0};
    long long int ma=b[0];
    for(int i=1;i<n+1;i++){
        int cost=reach[i-1].second;
        if(cost>=2*1e14) break;

        if(cost+a[i-1]>=0){
            reach[i]={reach[i-1].first+1,cost+a[i-1]};
        }
        else{
            if(ma==0){
                break;
            }
            int times=abs(cost+a[i-1])/ma+((cost+a[i-1])%ma!=0);
            reach[i]={reach[i-1].first+times+1,ma*times+cost+a[i-1]};
        }
        if(i==n) break;
        ma=max(ma,b[i]);
    }

    long long int res=0;
    ma=b[0];
    for(int i=0;i<=n;i++){
        if(reach[i].first<=n){
            long long int pl;
            pl=(n-reach[i].first)*ma;
            long long int val=reach[i].second;
            res=max(res,val+pl);
        }
        if(n-1<=i) continue;
        ma=max(ma,b[i+1]);
    }
    cout<<res<<endl;
    return 0;
}

Submission

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

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 0 / 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 74 ms 3328 KB
20_large_02.txt AC 86 ms 3328 KB
20_large_03.txt AC 85 ms 3328 KB
20_large_04.txt AC 74 ms 3328 KB
20_large_05.txt AC 86 ms 3328 KB
20_large_06.txt AC 86 ms 3328 KB
20_large_07.txt AC 75 ms 3328 KB
20_large_08.txt AC 98 ms 3328 KB
20_large_09.txt AC 89 ms 3328 KB
20_large_10.txt WA
20_large_11.txt WA
20_large_12.txt WA
20_large_13.txt AC 66 ms 3328 KB
20_large_14.txt AC 73 ms 3328 KB
20_large_15.txt AC 72 ms 3328 KB
20_large_16.txt AC 60 ms 3328 KB
20_large_17.txt AC 71 ms 3328 KB
20_large_18.txt AC 71 ms 3328 KB
20_large_19.txt WA
20_large_20.txt WA
20_large_21.txt WA
20_large_22.txt AC 57 ms 3328 KB
20_large_23.txt AC 69 ms 3328 KB
20_large_24.txt AC 68 ms 3328 KB
20_large_25.txt WA
20_large_26.txt WA
20_large_27.txt WA
20_large_28.txt WA
20_large_29.txt WA
20_large_30.txt AC 82 ms 3328 KB
30_run_through_01.txt WA
70_maximum_01.txt AC 95 ms 3328 KB
80_hand_01.txt AC 37 ms 3328 KB
80_hand_02.txt AC 34 ms 3328 KB
80_hand_03.txt AC 33 ms 3328 KB
80_hand_04.txt AC 33 ms 3328 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