Submission #1592067
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(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 Info
Submission Time |
|
Task |
D - 高橋君の旅行 |
User |
roto_37 |
Language |
C++14 (GCC 5.4.1) |
Score |
3 |
Code Size |
2162 Byte |
Status |
RE |
Exec Time |
201 ms |
Memory |
1536 KB |
Judge Result
Set Name |
Small |
All |
Score / Max Score |
3 / 3 |
0 / 197 |
Status |
|
|
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 |
20 ms |
1408 KB |
20_large_02.txt |
WA |
22 ms |
1536 KB |
20_large_03.txt |
WA |
22 ms |
1536 KB |
20_large_04.txt |
AC |
19 ms |
1408 KB |
20_large_05.txt |
WA |
22 ms |
1536 KB |
20_large_06.txt |
WA |
22 ms |
1536 KB |
20_large_07.txt |
AC |
20 ms |
1408 KB |
20_large_08.txt |
WA |
22 ms |
1536 KB |
20_large_09.txt |
WA |
22 ms |
1536 KB |
20_large_10.txt |
WA |
20 ms |
1408 KB |
20_large_11.txt |
WA |
22 ms |
1536 KB |
20_large_12.txt |
WA |
22 ms |
1536 KB |
20_large_13.txt |
WA |
18 ms |
1536 KB |
20_large_14.txt |
WA |
20 ms |
1536 KB |
20_large_15.txt |
WA |
20 ms |
1536 KB |
20_large_16.txt |
WA |
18 ms |
1536 KB |
20_large_17.txt |
RE |
201 ms |
1536 KB |
20_large_18.txt |
RE |
114 ms |
1536 KB |
20_large_19.txt |
WA |
19 ms |
1408 KB |
20_large_20.txt |
WA |
21 ms |
1536 KB |
20_large_21.txt |
WA |
21 ms |
1536 KB |
20_large_22.txt |
WA |
17 ms |
1536 KB |
20_large_23.txt |
WA |
19 ms |
1536 KB |
20_large_24.txt |
WA |
19 ms |
1536 KB |
20_large_25.txt |
WA |
19 ms |
1408 KB |
20_large_26.txt |
WA |
21 ms |
1536 KB |
20_large_27.txt |
WA |
21 ms |
1536 KB |
20_large_28.txt |
WA |
19 ms |
1408 KB |
20_large_29.txt |
WA |
21 ms |
1536 KB |
20_large_30.txt |
WA |
21 ms |
1536 KB |
30_run_through_01.txt |
WA |
20 ms |
1536 KB |
70_maximum_01.txt |
WA |
22 ms |
1536 KB |
80_hand_01.txt |
WA |
13 ms |
1536 KB |
80_hand_02.txt |
WA |
13 ms |
1536 KB |
80_hand_03.txt |
WA |
13 ms |
1536 KB |
80_hand_04.txt |
WA |
13 ms |
1536 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 |