oj.uz

Submission #1097400

# Submission time Handle Problem Language Result Execution time Memory
1097400 2024-10-07T08:21:24 Z alexdd Homecoming (BOI18_homecoming) C++17
62 / 100
 1000 ms 188588 KB 
#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
const long long INF = 1e18;
long long dp[6000005][2];
long long a[6000005],initb[6000005],b[6000005];
long long prefb[6000005];
long long calc(int N, int K, int p)
{
    long long aux=0;
    for(int i=1;i<=N;i++)
    {
        if(i<=p)
        {
            b[i] = b[i+N] = 0;
            aux += initb[i];
        }
        else
            b[i] = b[i+N] = initb[i];
    }
    for(int i=1;i<=2*N;i++)
    {
        prefb[i] = prefb[i-1] + b[i];
    }
    for(int i=0;i<K;i++)
    {
        dp[i][0]=0;
        dp[i][1]=-INF;
    }
    for(int i=K;i<N+K;i++)
    {
        dp[i][1] = max(dp[i-1][1]+a[i]-b[i], dp[i-K][0]+a[i]-(prefb[i]-prefb[i-K]));
        dp[i][0] = max({dp[i-1][0], dp[i-1][1], dp[i][1]});
    }
    return max(dp[N+K-1][0], dp[N+K-1][1]) - aux;
}
long long int solve(int N, int K, int *copA, int *copB)
{
    for(int i=0;i<N;i++)
    {
        a[i+K] = copA[i];
        initb[i+1] = copB[i];
    }
    long long rez=0;
    for(int p=0;p<=K;p++)
        rez = max(rez, calc(N,K,p));
    return rez;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 136 ms 860 KB Output is correct
7 Correct 108 ms 980 KB Output is correct
8 Correct 18 ms 604 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 35664 KB Output is correct
2 Correct 10 ms 348 KB Output is correct
3 Correct 169 ms 180812 KB Output is correct
4 Correct 11 ms 2136 KB Output is correct
5 Correct 17 ms 4148 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 136 ms 860 KB Output is correct
7 Correct 108 ms 980 KB Output is correct
8 Correct 18 ms 604 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 44 ms 35664 KB Output is correct
12 Correct 10 ms 348 KB Output is correct
13 Correct 169 ms 180812 KB Output is correct
14 Correct 11 ms 2136 KB Output is correct
15 Correct 17 ms 4148 KB Output is correct
16 Execution timed out 1084 ms 188588 KB Time limit exceeded
17 Halted 0 ms 0 KB -