oj.uz

Submission #97405

# Submission time Handle Problem Language Result Execution time Memory
97405 2019-02-15T18:06:14 Z georgerapeanu Homecoming (BOI18_homecoming) C++11
100 / 100
 318 ms 149456 KB 
#ifndef __HOMECOMING_H
#define __HOMECOMING_H
#include <cstdio>
#include <cassert>
#include <algorithm>

using namespace std;

const int NMAX = 2e6;
const int KMAX = 2e6;

int n;
long long dp[NMAX + 5][2];
long long prefA[NMAX + 5];
long long prefB[NMAX + 5];
long long prefdelta[NMAX + 5];

int A[NMAX + 5];
int B[NMAX + 5];

long long sum(int l,int r,long long pref[]){
    if(l <= r){
        return pref[r] - pref[l - 1];
    }
    return pref[n] - pref[l - 1] + pref[r];
}

long long solve(int N, int K, int *AA, int *BB){

    for(int i = 1;i <= N;i++){
        A[i] = AA[i - 1];
        B[i] = BB[i - 1];
    }
    
    n = N;
    for(int i = 1;i <= N;i++){
        prefA[i] = prefA[i - 1] + A[i];
        prefB[i] = prefB[i - 1] + B[i];
        prefdelta[i] = A[i] - B[i] + prefdelta[i - 1];
    }

    dp[1][1] = A[1]  - sum(1,K,prefB);

    long long mi = prefdelta[1] - dp[1][0],pos = 1;

    for(int i = 2;i <= N;i++){
        dp[i][0] = max(dp[i - 1][0], A[i] + (-sum(i,(i + K - 2) % N + 1,prefB)) + (prefdelta[i - 1] - mi));
        if(prefdelta[i] - dp[i][0] < mi){
            mi = prefdelta[i] - dp[i][0];
            pos = i;
        }
    }

    for(int i = 1;i <= K;i++){
        B[i] = 0;
    }

    for(int i = 1;i <= N;i++){
        prefA[i] = prefA[i - 1] + A[i];
        prefB[i] = prefB[i - 1] + B[i];
        prefdelta[i] = A[i] - B[i] + prefdelta[i - 1];
    }

    mi = prefdelta[1] - dp[1][1];
    pos = 1;

    for(int i = 2;i <= N;i++){
        dp[i][1] = max(dp[i - 1][1], A[i] + (-sum(i,(i + K - 2) % N + 1,prefB)) + (prefdelta[i - 1] - mi));
        if(prefdelta[i] - dp[i][1] < mi){
            mi = prefdelta[i] - dp[i][1];
            pos = i;
        }
    }

    return max(dp[N][1],dp[N][0]);
}
/*
int main() {
  int T; assert(scanf("%d", &T) == 1);
  for(int t = 0; t < T; t++) {
    int N, K; assert(scanf("%d%d", &N, &K) == 2);
    int *A = new int[N];
    int *B = new int[N];
    for(int i = 0; i < N; i++) assert(scanf("%d", &A[i]) == 1);
    for(int i = 0; i < N; i++) assert(scanf("%d", &B[i]) == 1);
    printf("%lld\n", solve(N, K, A, B));
    delete[] A;
    delete[] B;
  }
  return 0;
}*/
#endif

Compilation message

homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:44:44: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
     long long mi = prefdelta[1] - dp[1][0],pos = 1;
                                            ^~~

Subtask #1
13.0 / 13.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 664 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 4 ms 512 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 27776 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 318 ms 149456 KB Output is correct
4 Correct 5 ms 1792 KB Output is correct
5 Correct 13 ms 3800 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 664 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 60 ms 27776 KB Output is correct
12 Correct 5 ms 1024 KB Output is correct
13 Correct 318 ms 149456 KB Output is correct
14 Correct 5 ms 1792 KB Output is correct
15 Correct 13 ms 3800 KB Output is correct
16 Correct 287 ms 149340 KB Output is correct
17 Correct 134 ms 32144 KB Output is correct
18 Correct 202 ms 43768 KB Output is correct
19 Correct 256 ms 82516 KB Output is correct
20 Correct 248 ms 132588 KB Output is correct
21 Correct 182 ms 79964 KB Output is correct