oj.uz

Submission #61687

# Submission time Handle Problem Language Result Execution time Memory
61687 2018-07-26T10:34:59 Z hamzqq9 Homecoming (BOI18_homecoming) C++14
62 / 100
 1000 ms 79052 KB 
#include "homecoming.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000000000000
#define umax(x,y) x=max(x,(y))
#define pw(x) (1<<(x))

ll psum[2000002],psum2[2000002];
ll dp[2][2000002];

long long solve(int N, int K, int *A, int *B) {
  
  ll res=0;

  for(int i=1;i<=N;i++) {psum[i]=psum[i-1]+B[i-1];psum2[i]=psum2[i-1]+A[i-1];}
  
  for(int j=0;j<=K;j++) {
    
    for(int i=1;i<=N+1;i++) for(int t=0;t<2;t++) dp[t][i]=-inf; 

    dp[1][j+1]=(j-K+1>=1?A[j-K+1-1]:0)-psum[j];

    for(int i=j+1;i<=N;i++) {

      if(dp[1][i]!=-inf) {

        if(i<N) umax(dp[1][i+1],dp[1][i]-B[i-1]+(i-K+1>=1?A[i-K+1-1]:0));
        else {
          
          int amount=max(0,min(j+1,K));

          umax(dp[1][N+1],dp[1][i]-B[i-1]+psum2[i-K+amount]-psum2[i-K]);

        }

        umax(dp[0][i+1],dp[1][i]);

      }

      if(dp[0][i]!=-inf) {

        if(i+K<=N) {

          umax(dp[1][i+K],dp[0][i]+A[i-1]-(psum[i+K-1]-psum[i-1]));

        }
        else {

          int amount=max(0,min(N+1-i,j+N+1-i-K+1));

          umax(dp[1][N+1],dp[0][i]+psum2[i+amount-1]-psum2[i-1]-(psum[N]-psum[i-1]));

        }

        umax(dp[0][i+1],dp[0][i]);

      }

    }

    umax(res,max(dp[0][N+1],dp[1][N+1]));

  }
  
  umax(res,psum2[N]-psum[N]);

  return res;

}

Subtask #1
13.0 / 13.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 5 ms 544 KB Output is correct
5 Correct 4 ms 544 KB Output is correct
6 Correct 226 ms 792 KB Output is correct
7 Correct 188 ms 792 KB Output is correct
8 Correct 37 ms 792 KB Output is correct
9 Correct 11 ms 792 KB Output is correct
10 Correct 4 ms 792 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 20348 KB Output is correct
2 Correct 24 ms 20348 KB Output is correct
3 Correct 304 ms 79052 KB Output is correct
4 Correct 28 ms 79052 KB Output is correct
5 Correct 44 ms 79052 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 5 ms 544 KB Output is correct
5 Correct 4 ms 544 KB Output is correct
6 Correct 226 ms 792 KB Output is correct
7 Correct 188 ms 792 KB Output is correct
8 Correct 37 ms 792 KB Output is correct
9 Correct 11 ms 792 KB Output is correct
10 Correct 4 ms 792 KB Output is correct
11 Correct 107 ms 20348 KB Output is correct
12 Correct 24 ms 20348 KB Output is correct
13 Correct 304 ms 79052 KB Output is correct
14 Correct 28 ms 79052 KB Output is correct
15 Correct 44 ms 79052 KB Output is correct
16 Execution timed out 1075 ms 79052 KB Time limit exceeded
17 Halted 0 ms 0 KB -