Submission #1275780
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> P; #define EACH(i,a) for (auto&& i : a) #define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++) #define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--) #define REP(i,n) FOR(i,0,n) #define RREP(i,n) RFOR(i,0,n) #define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME #define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__) #define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__) #define debug(x) cout<<#x<<": "<<x<<endl #define pb push_back #define ALL(a) (a).begin(),(a).end() #define chmin(x,v) x = min(x, v) #define chmax(x,v) x = max(x, v) const ll linf = 1e18; const int inf = 1e9; const double eps = 1e-12; const double pi = acos(-1); template<typename T> istream& operator>>(istream& is, vector<T>& vec) { EACH(x,vec) is >> x; return is; } template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec) { REP(i,vec.size()) { if (i) os << " "; os << vec[i]; } return os; } template<typename T> ostream& operator<<(ostream& os, const vector< vector<T> >& vec) { REP(i,vec.size()) { if (i) os << endl; os << vec[i]; } return os; } int main() { ios::sync_with_stdio(false); cin.tie(0); ll n; cin >> n; vector<ll> A(n), B(n); cin >> A >> B; ll M = 0; ll money = 0; ll ans = 0; ll day = 0; chmax(ans, n*B[0]); rep(i, n) { chmax(M, B[i]); if (day <= n) { chmax(ans, money + M * (n-day)); } ll th = -A[i]; if (money < th) { if (M == 0) break; ll need = th-money; ll x = (need+M-1) / M; money += M * x; day += x; } money -= th; ++day; assert(money >= 0); } if (day <= n) { chmax(ans, money + M * (n-day)); } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 高橋君の旅行 |
User | drafear |
Language | C++14 (GCC 5.4.1) |
Score | 200 |
Code Size | 2086 Byte |
Status | AC |
Exec Time | 22 ms |
Memory | 1920 KB |
Judge Result
Set Name | Small | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 3 / 3 | 197 / 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 | 21 ms | 1792 KB |
20_large_02.txt | AC | 22 ms | 1792 KB |
20_large_03.txt | AC | 22 ms | 1920 KB |
20_large_04.txt | AC | 21 ms | 1792 KB |
20_large_05.txt | AC | 22 ms | 1792 KB |
20_large_06.txt | AC | 22 ms | 1792 KB |
20_large_07.txt | AC | 21 ms | 1792 KB |
20_large_08.txt | AC | 22 ms | 1792 KB |
20_large_09.txt | AC | 22 ms | 1792 KB |
20_large_10.txt | AC | 20 ms | 1920 KB |
20_large_11.txt | AC | 22 ms | 1792 KB |
20_large_12.txt | AC | 22 ms | 1792 KB |
20_large_13.txt | AC | 18 ms | 1792 KB |
20_large_14.txt | AC | 19 ms | 1792 KB |
20_large_15.txt | AC | 19 ms | 1792 KB |
20_large_16.txt | AC | 17 ms | 1792 KB |
20_large_17.txt | AC | 20 ms | 1792 KB |
20_large_18.txt | AC | 19 ms | 1792 KB |
20_large_19.txt | AC | 19 ms | 1792 KB |
20_large_20.txt | AC | 21 ms | 1792 KB |
20_large_21.txt | AC | 21 ms | 1792 KB |
20_large_22.txt | AC | 17 ms | 1792 KB |
20_large_23.txt | AC | 19 ms | 1792 KB |
20_large_24.txt | AC | 19 ms | 1792 KB |
20_large_25.txt | AC | 19 ms | 1792 KB |
20_large_26.txt | AC | 21 ms | 1792 KB |
20_large_27.txt | AC | 21 ms | 1792 KB |
20_large_28.txt | AC | 20 ms | 1792 KB |
20_large_29.txt | AC | 21 ms | 1792 KB |
20_large_30.txt | AC | 21 ms | 1792 KB |
30_run_through_01.txt | AC | 20 ms | 1792 KB |
70_maximum_01.txt | AC | 22 ms | 1792 KB |
80_hand_01.txt | AC | 13 ms | 1792 KB |
80_hand_02.txt | AC | 13 ms | 1792 KB |
80_hand_03.txt | AC | 13 ms | 1792 KB |
80_hand_04.txt | AC | 13 ms | 1792 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 |