oj.uz

Submission #853027

# Submission time Handle Problem Language Result Execution time Memory
853027 2023-09-23T10:42:58 Z Benmath Homecoming (BOI18_homecoming) C++14
100 / 100
 228 ms 188576 KB 
#include<homecoming.h>
#include<bits/stdc++.h>
using namespace std;
long long int calculate (int i, int j, long long int prefiks[]){
    if(i == 0){
        return prefiks[j];
    }else{
        return prefiks[j] - prefiks[i-1];
    }
}
long long solve(int N, int K, int *A, int *B){
    int n = N;
    int k = K;
    long long int a[n];
    long long int b[n];
    long long int dp[n];
    long long int dp1[n];
    long long int sum1 = 0;
    long long int pref1[2*n+1];
    long long int pref2[2*n+1];
    for(int i = 0; i < n; i++){
        a[i] = A[i];
        b[i] = B[i];
        sum1 = sum1 + a[i] - b[i];
       
        dp[i] = 0;
        dp1[i] = -1e18;
    }
    pref1[0] = a[0];
    pref2[0] = b[0];
    for(int i = 1; i <= 2*n; i++){
        pref1[i] = pref1[i-1] + a[i % n];
        pref2[i] = pref2[i-1] + b[i % n];
    }
    long long int ans = 0;
    
    ans = max (ans, sum1);
    // ako ne uzimamo prvi element
    for(int i = 0; i < n; i++){
        if (i == 0){
            long long int sum = calculate(i, i + k-1, pref2);
            dp1[i] = a[i] - sum;
            
           // dp[i] = max(dp[i], dp1[i]);
           dp[i] = 0;
           dp1[i] = -1e18;
        }else{
            dp[i] = dp[i-1];
            long long int sum = calculate(i, i + k - 1, pref2);
            
            sum = a[i] - sum;
            if (i >= k){
                dp1[i] = sum + dp[i-k];
            }else{
                dp1[i] = sum;
            }
         
            dp1[i] = max(dp1[i], dp1[i-1] + a[i] - b[(i + k - 1) % n] );
            dp[i] = max(dp[i], dp1[i]);
        }
    }
    
    ans = max(ans, dp[n-1]);
    
    // ako uzimamo prvi element
    int vis[n];
    for (int i = 0; i < n; i++){
        dp[i] = -1e18;
        dp1[i] = -1e18;
        vis[i] = 0;
    }
    for (int i = 0; i < n; i++){
        if (i == 0){
            long long int sum = 0;
             sum = calculate(i, i + k-1, pref2);
            dp1[i] = a[i] - sum;
            dp[i] = dp1[i];
        }else{
            if (i >= k){
                dp[i] = dp[i-1];
                long long int sum = 0;
                sum = calculate(i, i + k-1, pref2);
                sum = a[i] - sum;
               
                dp1[i] = sum + dp[i-k];
                long long int ro = a[i];
                ro = ro - b[(i + k - 1) % n];
                dp1[i] = max(dp1[i], dp1[i-1] + ro);
            
                dp[i] = max(dp[i], dp1[i]);
                sum = 0;
                sum = calculate (i, n - 1, pref1) - calculate(i, n - 1, pref2);
                ans = max(ans, sum + dp[i-k]);
            }else{
                dp[i] = dp[i-1];
                long long int ro = a[i]; 
                if(vis[(i + k - 1) % n] == 0){
                    ro = ro - b[(i + k - 1) % n];
                }
                dp1[i] =  dp1[i-1] + ro;
                dp[i] = max(dp[i], dp1[i]);
            }
        }
    }
    ans = max(ans, dp[n-1]);
   return ans;
    
}

Subtask #1
13.0 / 13.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 37456 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 193 ms 188576 KB Output is correct
4 Correct 2 ms 2136 KB Output is correct
5 Correct 9 ms 4136 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 44 ms 37456 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 193 ms 188576 KB Output is correct
14 Correct 2 ms 2136 KB Output is correct
15 Correct 9 ms 4136 KB Output is correct
16 Correct 228 ms 188476 KB Output is correct
17 Correct 71 ms 36728 KB Output is correct
18 Correct 128 ms 45580 KB Output is correct
19 Correct 142 ms 102160 KB Output is correct
20 Correct 161 ms 171552 KB Output is correct
21 Correct 152 ms 99588 KB Output is correct