oj.uz

Submission #861660

# Submission time Handle Problem Language Result Execution time Memory
861660 2023-10-16T15:49:25 Z Aiperiii Homecoming (BOI18_homecoming) C++17
100 / 100
 111 ms 102484 KB 
#include "homecoming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
const int N=2e6+6;
ll dp[N][2];
ll solve(int n,int k,int a[],int b[]){
    vector <ll> pr;
    ll sum=0;
    for(int i=0;i<n;i++){
        sum+=b[i];
        pr.push_back(sum);
    }
    dp[0][0]=-1e18;
    dp[0][1]=a[0]-pr[k-1];
    for(int i=1;i<n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        ll val1=dp[i-1][1]+a[i];
        if(i+k-1<n){
            val1-=b[i+k-1];
        }
        ll val2=dp[i-1][0]+a[i]-pr[min(i+k-1,n-1)]+pr[i-1];
        dp[i][1]=max(val1,val2);
    }
    ll res1=max(dp[n-1][0],dp[n-1][1]);
    dp[0][0]=0;
    dp[0][1]=-1e18;
    for(int i=1;i<n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        ll val1=dp[i-1][1]+a[i]-b[(i+k-1)%n];
        ll val2=dp[i-1][0]+a[i]-pr[min(i+k-1,n-1)]+pr[i-1];
        if(i+k-1>n-1){
            val2-=pr[i+k-1-n];
        }
        dp[i][1]=max(val1,val2);
    }
    ll res2=max(dp[n-1][0],dp[n-1][1]);
    return max(res1,res2);
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26184 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 111 ms 102484 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 7 ms 5100 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 30 ms 26184 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 111 ms 102484 KB Output is correct
14 Correct 2 ms 3540 KB Output is correct
15 Correct 7 ms 5100 KB Output is correct
16 Correct 110 ms 102364 KB Output is correct
17 Correct 54 ms 26128 KB Output is correct
18 Correct 108 ms 42088 KB Output is correct
19 Correct 88 ms 68140 KB Output is correct
20 Correct 78 ms 85704 KB Output is correct
21 Correct 83 ms 57348 KB Output is correct