oj.uz

Submission #745130

# Submission time Handle Problem Language Result Execution time Memory
745130 2023-05-19T12:22:49 Z danikoynov Measures (CEOI22_measures) C++14
10 / 100
 1500 ms 13444 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

const int maxn = 4e5 + 10;

ll n, m, a[maxn], b[maxn], D, act[2][maxn], used[maxn];
ll pref[maxn], suff[maxn];
pair < ll, ll > p[maxn];
void solve()
{
    cin >> n >> m >> D;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], p[i] = {a[i], i};
    for (int j = 1; j <= m; j ++)
        cin >> b[j], p[n + j] = {b[j], n + j};

    sort(p + 1, p + n + m + 1);
    for (int i = 1; i <= n + m; i ++)
    {
        if (p[i].second <= n)
        {
            act[0][p[i].second] = i;
        }
        else
        {
            act[1][p[i].second - n] = i;
        }
    }
    /// 0.5 * ((j - i) * D - (a[j] - a[i]));
    //for (int i = 1; i <= n + m; i ++)
      //  cout << p[i].first << " : " << p[i].second << endl;
    ll ans = 0;
    for (ll i = 1; i <= n + m; i ++)
    { ll idx;
    if (i <= n)
        idx = act[0][i];
        else
            idx = act[1][i - n];

        used[idx] = 1;
        ll cnt = 0;
        for (ll j = 1; j < idx; j ++)
        {

            if (!used[j])
                continue;
            cnt ++;   ///cout << "point " << j << endl;
        }
        cnt ++;
        pref[idx] = + p[idx].first - cnt * D;
        suff[idx] = - p[idx].first + cnt * D;
        //cout << i << " : " << pref[idx] << " " << suff[idx] << " " << cnt << " " << idx << endl;
        for (int j = idx + 1; j <= n + m; j ++)
        {
            if (!used[j])
                continue;
            pref[j] = pref[j] - D;
            suff[j] = suff[j] + D;
        }

        ll mx_pref = -1e18, mx_suff = -1e18;
        for (int j = 1; j < idx; j ++)
        {
            if (!used[j])
                continue;
                ///cout << "pref " << suff[idx] + pref[j] << " " << pref[j] << endl;
                mx_pref = max(mx_pref, pref[j]);
            ///ans = max(ans, suff[idx] + pref[j]);
        }
        for (int j = idx + 1; j <= n + m; j ++)
        {
            if (!used[j])
                continue;
                mx_suff = max(mx_suff, suff[j]);
            ///ans = max(ans, pref[idx] + suff[j]);
        }
        ans = max(ans, mx_pref + mx_suff);
        ans = max(ans, pref[idx] + mx_suff);
        ans = max(ans, suff[idx] + mx_pref);
        ///cout << ans << endl;
        if (i > n)
        {
            if (ans % 2 == 0)
                cout << ans / 2 << " ";
            else
                cout << ans / 2 << ".5 ";
        }
    }
    cout << endl;
}
int main()
{
    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:66:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   66 |             if (!used[j])
      |             ^~
Main.cpp:69:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   69 |                 mx_pref = max(mx_pref, pref[j]);
      |                 ^~~~~~~
Main.cpp:74:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   74 |             if (!used[j])
      |             ^~
Main.cpp:76:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   76 |                 mx_suff = max(mx_suff, suff[j]);
      |                 ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 468 KB Output is correct
2 Correct 8 ms 448 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Correct 9 ms 448 KB Output is correct
5 Correct 8 ms 484 KB Output is correct
6 Correct 8 ms 484 KB Output is correct
7 Correct 18 ms 468 KB Output is correct
8 Correct 8 ms 468 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 468 KB Output is correct
2 Correct 8 ms 448 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Correct 9 ms 448 KB Output is correct
5 Correct 8 ms 484 KB Output is correct
6 Correct 8 ms 484 KB Output is correct
7 Correct 18 ms 468 KB Output is correct
8 Correct 8 ms 468 KB Output is correct
9 Execution timed out 1572 ms 13444 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1569 ms 8796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1569 ms 8796 KB Time limit exceeded
2 Halted 0 ms 0 KB -