Submission #1720731
Source Code Expand
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } //--------------------------------------------------------------------------------------------------- /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ int N, T[101], V[101]; double dp[105][105]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> T[i]; rep(i, 0, N) cin >> V[i]; dp[0][0] = 1; rep(i, 0, N) rep(v, 0, 105) if (dp[i][v] and v <= V[i]) { rep(vv, 0, 105) if(vv <= V[i]) { int a = V[i] - v; int b = V[i] - vv; if (a + b <= T[i]) { double up = 1.0 * (v + V[i]) * a / 2; double stay = V[i] * (T[i] - a - b); double down = 1.0 * (vv + V[i]) * b / 2; double c = up + stay + down; dp[i + 1][vv] = max(dp[i + 1][vv], dp[i][v] + c); } else if (T[i] < abs(vv - v)) { // can't } else { // v + x = vv + y // x + y = T[i] // x - y = vv - v // x + y = T[i] // 2x = vv - v + T[i] // x = (vv - v + T[i]) / 2 // y = T[i] - x // = T[i] - (vv - v + T[i]) / 2 // = (T[i] - vv + v) / 2 double x = 1.0 * (vv - v + T[i]) / 2; double y = 1.0 * (T[i] - vv + v) / 2; double vvv = v + x; double up = 1.0 * (v + vvv) * x / 2; double down = 1.0 * (vv + vvv) * y / 2; double c = up + down; dp[i + 1][vv] = max(dp[i + 1][vv], dp[i][v] + c); } } } printf("%.10f\n", dp[N][0] - 1); }
Submission Info
Submission Time | |
---|---|
Task | D - AtCoder Express |
User | hamayanhamayan |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 2587 Byte |
Status | AC |
Exec Time | 5 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt, s3.txt, s4.txt, s5.txt |
All | in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, s1.txt, s2.txt, s3.txt, s4.txt, s5.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in01.txt | AC | 1 ms | 256 KB |
in02.txt | AC | 1 ms | 256 KB |
in03.txt | AC | 1 ms | 256 KB |
in04.txt | AC | 1 ms | 256 KB |
in05.txt | AC | 2 ms | 384 KB |
in06.txt | AC | 2 ms | 384 KB |
in07.txt | AC | 2 ms | 384 KB |
in08.txt | AC | 2 ms | 384 KB |
in09.txt | AC | 2 ms | 384 KB |
in10.txt | AC | 2 ms | 384 KB |
in11.txt | AC | 2 ms | 384 KB |
in12.txt | AC | 1 ms | 384 KB |
in13.txt | AC | 1 ms | 384 KB |
in14.txt | AC | 1 ms | 384 KB |
in15.txt | AC | 1 ms | 256 KB |
in16.txt | AC | 2 ms | 384 KB |
in17.txt | AC | 2 ms | 384 KB |
in18.txt | AC | 2 ms | 384 KB |
in19.txt | AC | 1 ms | 256 KB |
in20.txt | AC | 1 ms | 384 KB |
in21.txt | AC | 1 ms | 384 KB |
in22.txt | AC | 1 ms | 384 KB |
in23.txt | AC | 1 ms | 256 KB |
in24.txt | AC | 1 ms | 384 KB |
in25.txt | AC | 1 ms | 384 KB |
in26.txt | AC | 5 ms | 384 KB |
in27.txt | AC | 5 ms | 384 KB |
in28.txt | AC | 1 ms | 256 KB |
in29.txt | AC | 1 ms | 256 KB |
in30.txt | AC | 1 ms | 256 KB |
in31.txt | AC | 1 ms | 384 KB |
in32.txt | AC | 1 ms | 384 KB |
in33.txt | AC | 1 ms | 384 KB |
in34.txt | AC | 1 ms | 384 KB |
in35.txt | AC | 1 ms | 384 KB |
s1.txt | AC | 1 ms | 256 KB |
s2.txt | AC | 1 ms | 256 KB |
s3.txt | AC | 1 ms | 256 KB |
s4.txt | AC | 1 ms | 256 KB |
s5.txt | AC | 1 ms | 256 KB |