Submission #1592069


Source Code Expand

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

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const ll mod = 10000;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

#define int long long
#define addm(X, Y) ((X) = ((X) + (Y) % mod) % mod)

int n;
int a[100000 + 5], b[100000 + 5];
int mx[100000 + 5];
pair<ll, ll> dp[10000 + 5];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    rep(i, n) cin >> a[i];
    rep(i, n) {
        cin >> b[i];
        mx[i] = max(mx[max(0LL, i - 1)], b[i]);
    }
    dp[0].fi = 0;
    dp[0].se = 0;
    int lim = -1;
    rep(i, n) {
        int cnt = 0;
        int tmp = dp[i].se + a[i];
        if (tmp < 0) {
            if (mx[i] == 0) {
                lim = i;
                break;
            }
            cnt += -(tmp + 1) / mx[i] + 1;
            tmp = tmp + mx[i] * cnt;
        }
        if (dp[i].fi + cnt + 1 > n) {
            lim = i;
            break;
        }
        dp[i + 1].fi = dp[i].fi + cnt + 1;
        dp[i + 1].se = tmp;
        lim = max(lim, i + 1);
    }
    ll ans = 0;
    rep(i, lim + 1) ans = max(ans, dp[i].se + (n - dp[i].fi) * mx[i]);
    cout << ans << endl;
}

Submission Info

Submission Time
Task D - 高橋君の旅行
User roto_37
Language C++14 (GCC 5.4.1)
Score 3
Code Size 2162 Byte
Status WA
Exec Time 22 ms
Memory 2816 KB

Judge Result

Set Name Small All
Score / Max Score 3 / 3 0 / 197
Status
AC × 13
AC × 17
WA × 32
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 19 ms 2560 KB
20_large_02.txt WA 22 ms 2816 KB
20_large_03.txt WA 22 ms 2816 KB
20_large_04.txt AC 19 ms 2560 KB
20_large_05.txt WA 22 ms 2816 KB
20_large_06.txt WA 22 ms 2816 KB
20_large_07.txt AC 19 ms 2560 KB
20_large_08.txt WA 22 ms 2816 KB
20_large_09.txt WA 22 ms 2816 KB
20_large_10.txt AC 20 ms 2688 KB
20_large_11.txt WA 22 ms 2816 KB
20_large_12.txt WA 22 ms 2816 KB
20_large_13.txt WA 18 ms 2816 KB
20_large_14.txt WA 20 ms 2816 KB
20_large_15.txt WA 20 ms 2816 KB
20_large_16.txt WA 18 ms 2816 KB
20_large_17.txt WA 20 ms 2816 KB
20_large_18.txt WA 20 ms 2816 KB
20_large_19.txt WA 19 ms 2816 KB
20_large_20.txt WA 21 ms 2816 KB
20_large_21.txt WA 21 ms 2816 KB
20_large_22.txt WA 17 ms 2816 KB
20_large_23.txt WA 19 ms 2816 KB
20_large_24.txt WA 19 ms 2816 KB
20_large_25.txt WA 19 ms 2816 KB
20_large_26.txt WA 21 ms 2816 KB
20_large_27.txt WA 21 ms 2816 KB
20_large_28.txt WA 19 ms 2816 KB
20_large_29.txt WA 21 ms 2816 KB
20_large_30.txt WA 21 ms 2816 KB
30_run_through_01.txt WA 21 ms 2688 KB
70_maximum_01.txt WA 22 ms 2816 KB
80_hand_01.txt WA 14 ms 2816 KB
80_hand_02.txt WA 13 ms 2816 KB
80_hand_03.txt WA 13 ms 2816 KB
80_hand_04.txt WA 13 ms 2816 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