Submission #69771

#TimeUsernameProblemLanguageResultExecution timeMemory
697713zpHomecoming (BOI18_homecoming)C++14
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> //#include "homecoming.h" using namespace std; int N1; long long sa[2000009], sb[2000009]; long long Sb(long long l, long long r){ if(!l) return sb[r]; if(l <= r) return sb[r] - sb[l-1]; return sb[N1-1] - sb[l - 1] + sb[r]; } long long Sa(long long l, long long r){ if(!l) return sa[r]; if(l <= r) return sa[r] - sa[l-1]; return sa[N1-1] - sa[l - 1] + sa[r]; } long long su(long long l, long long r){ return Sa(l,r) - Sb(l,r); } long long M[2000009][22]; long long dp[4000009][2]; long long A1[6000009]; long long B1[6000009]; long long int solve(int N, int K, int *A, int *B){ //if(N > 1e5) return 1/0; N1 = N; for(long long i = 0; i < N; i++) A1[i] = A[i], B1[i] = B[i]; for(long long i = 0; i < 2*N; i++) A1[i+N] = A1[i], B1[i+N] = B1[i]; sa[0] = A1[0]; sb[0] = B1[0]; for(long long i = 1; i < N; i++) sa[i] = sa[i-1] + A1[i], sb[i] = sb[i-1] + B1[i]; for(int i = 0 ;i < N; i++) M[i][0] = su(i,i); for(long long i = 1; (1 << i) < N; i++){ for(long long j = 0; j < N; j++){ long long m1 = M[j][i-1]; long long m2 = M[(j+(1<<(i-1)))%N][i-1]; M[j][i] = max(m2, m1 + su(j+(1<<i-1), j+(1<<i) - 1)); } } long long masof = 1e18, FI = -1; for(long long i = N; i < 2*N; i++){ long long S = A1[i] - Sb(i, i+K-1); long long x = i, ss = 0; for(long long L = 21; L >= 0; L--){ if(x - (1<<L) < 0) continue; if(M[(x - (1<<L))%N][L] + ss + S >= 0) continue; ss += su(x - (1 << L), x -1); x = x - (1 << L); } int l; if(S >= 0) l = i; else l = x - 1; if(l <= i - N) l = -1; if(l != -1 && masof > i - l) { FI = i; masof = i - l; } } if(FI == -1 || N == K) return max((long long)0, sa[N-1] - sb[N-1]); FI -= N; dp[FI][0] = -1e18; dp[FI][1] = A1[FI] - Sb(FI, FI+K-1); for(long long i = FI + 1; i < FI + N - K; i++){ dp[i][0] = max(dp[i-1][0] , dp[i-1][1]); dp[i][1] = dp[i-1][1] + A1[i] - B1[i + K - 1]; if(i - K >= FI) dp[i][1] =max(dp[i][1], max(dp[i - K][0] , dp[i - K][1]) + A1[i] - Sb(i, i+K-1)); } long long ans = max(dp[FI + N - K - 1][0], dp[FI+ N - K - 1][1]); long long s = 0; for(long long i = FI - 1; i > FI - N + K; i --){ s += A1[i+N] - B1[i+N]; ans =max(ans, s + max(dp[i + N - K - 1][0], dp[i + N - K - 1][1])); } return max(max((long long)0,ans), sa[N-1]-sb[N-1]); return 0; } int a[100009], b[100009]; long long ans[100009]; main(){ /* int t; cin>>t; int T= t; vector<long long >v; for(int i = 0; i <t; i++){ cin >> ans[i]; }*/ vector<long long> v; int t; cin>>t; while(t--){ long long n, K; cin >> n >> K; for(long long i= 0 ; i < n; i++) cin >> a[i]; for(long long i = 0; i < n; i++){ cin >> b[i]; } v.push_back( solve(n, K, a, b) ); cout<<v.back()<<endl; //if(v.back() != ans[T-t-1]) cout << ans[T-t-1]<<"!!!!", cin >> n; } for(int i = 0; i < v.size(); i++) cout<<v[i] <<endl; }/* 10 3 2 3 2 3 2 4 2 6 3 2 1 2 0 8 0 2 1 2 15 0 */

Compilation message (stderr)

homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:44:37: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
                           su(j+(1<<i-1), j+(1<<i) - 1));
                                    ~^~
homecoming.cpp: At global scope:
homecoming.cpp:89:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
homecoming.cpp: In function 'int main()':
homecoming.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); i++)
                    ~~^~~~~~~~~~
/tmp/ccVS4jPj.o: In function `main':
homecoming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccTbr8XN.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status