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

Submission #1592067

Source codeソースコード

#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(0, 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

Task問題 D - 高橋君の旅行
User nameユーザ名 roto_37
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 3
Source lengthソースコード長 2162 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 20 ms 1408 KB
20_large_02.txt WA
20_large_03.txt WA
20_large_04.txt AC 19 ms 1408 KB
20_large_05.txt WA
20_large_06.txt WA
20_large_07.txt AC 20 ms 1408 KB
20_large_08.txt WA
20_large_09.txt WA
20_large_10.txt WA
20_large_11.txt WA
20_large_12.txt WA
20_large_13.txt WA
20_large_14.txt WA
20_large_15.txt WA
20_large_16.txt WA
20_large_17.txt RE
20_large_18.txt RE
20_large_19.txt WA
20_large_20.txt WA
20_large_21.txt WA
20_large_22.txt WA
20_large_23.txt WA
20_large_24.txt WA
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 WA
30_run_through_01.txt WA
70_maximum_01.txt WA
80_hand_01.txt WA
80_hand_02.txt WA
80_hand_03.txt WA
80_hand_04.txt WA
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