Submission #1724697

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <limits>
#include <queue>
#include <iomanip>
#include <deque>
#include <stack>
#include <cstdio>
#include <cmath>
#include <complex.h>
#include <cstdio>
#include <random>
#include <chrono>
#include <numeric>
#include <cassert>
#include <iso646.h>
#include <exception>
#include <stdexcept>

using namespace std;

typedef long long i64;

double max_dist[40200][202];
int max_v[40200];

int tm_[100];
int velocity[100];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> tm_[i];
    for (int i = 0; i < n; i++) cin >> velocity[i];

    int cur_t = 0;
    int t_n = 0;
    for (int i = 0; i < n; i++)
    {
        const int t = tm_[i];
        const int v = velocity[i];

        if (cur_t > 0)
            max_v[cur_t - 1] = min(max_v[cur_t - 1], 2 * v);

        t_n += 2 * t;
        while (cur_t <= t_n)
        {
            max_v[cur_t] = 2 * v;
            cur_t++;
        }
    }

    for (int t = 0; t < 40200; t++)
        for (int v = 0; v < 202; v++)
            max_dist[t][v] = -1e18;

    max_dist[0][0] = 0;
    for (int t = 1; t <= t_n; t++)
        for (int cur_v = 0; cur_v <= max_v[t]; cur_v++)
            for (int shift = -1; shift <= 1; shift++)
            {
                const int prev_v = cur_v + shift;
                if (prev_v >= 0)
                {
                    double d = prev_v / 4.0;
                    if (shift < 0)
                        d += 1.0 / 8;
                    else if (shift > 0)
                        d -= 1.0 / 8;
                    max_dist[t][cur_v] = max(max_dist[t][cur_v], max_dist[t - 1][prev_v] + d);
                }
            }

    cout << max_dist[t_n][0];
}

Submission Info

Judge Result