SHARE
TWEET

Untitled

a guest Jan 20th, 2013 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cassert>
  5. #define MAXN 100005
  6. #define VAL(x) (x.first)
  7. #define COLOR(x) (x.second)
  8. using namespace std;
  9.  
  10. typedef long long int ll;
  11. int N, Q, C[MAXN];
  12. ll best[MAXN],V[MAXN], A, B, ans;
  13. bool visit[MAXN];
  14. pair<ll,int> t1,t2,cur;
  15.  
  16. ////USE COUT FOR LONG LONG!!!
  17. /*
  18.   same A
  19.   different B
  20.   first B
  21. */
  22. int main(){
  23.  // freopen("C.in","r",stdin);
  24.  // freopen("C.out","w",stdout);
  25.   scanf("%d%d",&N, &Q);
  26.   for(int i=1;i<=N;++i) cin >> V[i];
  27.   for(int i=1;i<=N;++i) scanf("%d",&C[i]);
  28.   for(int z=0;z<Q;++z){
  29.     cin >> A >> B;
  30.     if(A <= 0 && B <= 0){
  31.       printf("0\n");
  32.       continue;
  33.     }
  34.     //Init
  35.     t1 = pair<ll,int>(0,0);
  36.     t2 = pair<ll,int>(0,-1);
  37.     ans = 0;
  38.     memset(visit,0,sizeof(visit));
  39.  
  40.     for(int i=1;i<=N;++i){
  41.       //Compute
  42.       cur = pair<ll,int>(B * V[i],C[i]); //first
  43.       //get different colour
  44.       if(COLOR(t1) != COLOR(cur) && VAL(t1) > 0) VAL(cur) += VAL(t1);
  45.       else if(COLOR(t2) != COLOR(cur) && VAL(t2) > 0) VAL(cur) += VAL(t2);
  46.       //get same color
  47.       if(visit[C[i]]) VAL(cur) = max(VAL(cur), best[C[i]] + A * V[i]);
  48.       ans = max(ans,VAL(cur));
  49.       //Update
  50.       if(!visit[C[i]]) best[C[i]] = VAL(cur);
  51.       else best[C[i]] = max(VAL(cur),best[C[i]]);
  52.       visit[C[i]] = 1;
  53.       //cur has different color from both t1 and t2
  54.       if(COLOR(cur) != COLOR(t1) && COLOR(cur) != COLOR(t2)){
  55.         if(VAL(cur) >= VAL(t1)){
  56.           t2 = t1;
  57.           t1 = cur;
  58.         }
  59.         else if(VAL(cur) > VAL(t2)) t2 = cur;
  60.       }
  61.       //cur has same color with EXACTLY one of them
  62.       else{
  63.         if(COLOR(cur) == COLOR(t1)) VAL(t1) = max(VAL(t1),VAL(cur));
  64.         else VAL(t2) = max(VAL(t2),VAL(cur));
  65.         if(VAL(t1) < VAL(t2)) swap(t1,t2);
  66.       }
  67.       assert(VAL(t1) >= VAL(t2));
  68.       assert(COLOR(t1) != COLOR(t2));
  69.     }
  70.     cout << ans << endl;
  71.   }
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top