Submission #338403

#TimeUsernameProblemLanguageResultExecution timeMemory
338403couplefireHomecoming (BOI18_homecoming)C++17
Compilation error
0 ms0 KiB
#include "homecoming.h" #include <bits/stdc++.h> using namespace std; #define INF 1000000000000000009ll long long solve(int n, int k, vector<int> arr, vector<int> brr){ 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){ badpos = i%n; 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(); 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 (stderr)

homecoming.cpp: In function 'long long int solve(int, int, std::vector<int>, std::vector<int>)':
homecoming.cpp:47:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     while(arr.size() > n) arr.pop_back();
      |           ~~~~~~~~~~~^~~
homecoming.cpp:48:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     while(brr.size() > n) brr.pop_back();
      |           ~~~~~~~~~~~^~~
/tmp/ccLQ8j0m.o: In function `main':
grader.cpp:(.text.startup+0xee): undefined reference to `solve(int, int, int*, int*)'
collect2: error: ld returned 1 exit status