oj.uz

Submission #338570

# Submission time Handle Problem Language Result Execution time Memory
338570 2020-12-23T12:49:46 Z couplefire Homecoming (BOI18_homecoming) C++17
31 / 100
 267 ms 110252 KB 
#include "homecoming.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000009ll

long long solve(int n, int k, int *A, int *B){
    vector<int> arr, brr;
    for(int i = 0; i<n; i++) arr.push_back(A[i]), brr.push_back(B[i]);
    for(int i = 0; i<n; i++) arr.push_back(arr[i]);
    for(int i = 0; i<n; i++) brr.push_back(brr[i]);
    long long cursum = 0;
    deque<pair<long long, int>> dq;
    long long sum = 0;
    for(int i = 0; i<n; i++) sum += arr[i]-brr[i];
    if(k == n){
        return sum;
    }
    for(int i = n; i<n+n-k-1; i++){
        cursum += arr[i]-brr[i];
        if(dq.empty() || dq.front().first > cursum) dq.push_front({cursum, i});
    }
    long long minLen[n];
    long long shift = 0;
    for(int i = n-1; i>=0; i--){
        while(!dq.empty() && dq.front().second >= i+n-k) dq.pop_front();
        shift += arr[i]-brr[i];
        while(!dq.empty() && dq.back().first >= arr[i]-brr[i]-shift) dq.pop_back();
        dq.push_back({arr[i]-brr[i]-shift, i});
        minLen[i%n] = dq.front().first+shift;
    }
    // cout << minLen[0] << endl;
    cursum = 0;
    for(int i = 0; i<k-1; i++) cursum += arr[i];
    int badpos = -1;
    for(int i = k-1; i<=n+k; i++){
        if(minLen[i%n]+cursum < 0){
            long long csum = 0;
            for(int j = i; j<i+n-k; j++){
                csum += arr[j]-brr[j];
                if(csum + cursum < 0){
                    badpos = j%n;
                    break;
                }
            }
            break;
        }
        cursum -= arr[i-k+1];
        cursum += arr[i];
    }
    if(badpos == -1){
        // cout << "HI" << endl;
        return sum;
    }
    // cout << badpos << endl;
    for(int i = 0; i<n; i++) arr[i] = arr[i+badpos];
    for(int i = 0; i<n; i++) brr[i] = brr[i+badpos];
    while(arr.size() > n) arr.pop_back();
    while(brr.size() > n) brr.pop_back();
    // for(int i = 0; i<n; i++) cout << arr[i] << " ";
    // cout << endl;
    // for(int i = 0; i<n; i++) cout << brr[i] << " ";
    // cout << endl;
    cursum = 0;
    long long prefix[n];
    for(int i = 0; i<n; i++) cursum += brr[i], prefix[i] = cursum;
    long long dp[n][2];
    dp[0][0] = 0;
    dp[0][1] = -INF;
    if(k == 1) dp[0][1] = arr[0]-brr[0];
    for(int i = 1; i<n; i++){
        dp[i][0] = 0, dp[i][1] = -INF;
        dp[i][0] += max(dp[i-1][0], dp[i-1][1]);
        if(i == k-1) dp[i][1] = arr[0]-prefix[i];
        else if(i > k-1) dp[i][1] = max(dp[i-1][1]+arr[i-k+1]-brr[i], dp[i-k][0]-prefix[i]+prefix[i-k]+arr[i-k+1]);
    }
    // cout << dp[2][1] << endl;
    return max(dp[n-1][0], dp[n-1][1]);
}

Compilation message

homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:57:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     while(arr.size() > n) arr.pop_back();
      |           ~~~~~~~~~~~^~~
homecoming.cpp:58:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     while(brr.size() > n) brr.pop_back();
      |           ~~~~~~~~~~~^~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 27976 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 267 ms 110252 KB Output is correct
4 Correct 3 ms 1640 KB Output is correct
5 Correct 16 ms 1884 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -