Submission #115026

#	Time	Username	Problem	Language	Result	Execution time	Memory
115026		Dung	Two Dishes (JOI19_dishes)	C++11	0 / 100	10100 ms	32244 KiB

dishes

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int N,M;
struct c{
    long val;
    vector<int> lis;
};
vector<c> A;
vector<c> B;
vector<long long> S;
vector<long long> T;
vector<long> P;
vector<long> Q;
vector<long> suma, sumb;
unsigned long sum = 0;
vector<int> lima,limb;
long total = 0;

int Up(const vector<c>& AS, int value){
    for(int i = 0;i<AS.size();i++){
        if(AS[i].val > value){
            return i;
        }
    }
    return -1;
}

int dp(const int& curposa,const int& curposb,const short& state){
    int result = 0;

    if(curposa >= (int)lima.size() || curposb >= (int)limb.size()){
        return 0;
    }
    else{
        if(state == 1){
            int pos = curposb < (int)limb.size() - 1 ? limb[curposb + 1] - 1 : limb[curposb];
            int pos1 = lima[curposa];
            for(int i = 0;i<B[pos1].lis.size();i++){
                result += B[pos1].lis[i] <= pos ? 0 : P[B[pos1].lis[i]];
            }
        }
        else{
            int pos = curposa < (int)lima.size() - 1 ? lima[curposa + 1] - 1 : lima[curposa];
            int pos1 = limb[curposb];
            for(int i = 0;i<A[pos1].lis.size();i++){
                result += A[pos1].lis[i] <= pos ? 0 : Q[A[pos1].lis[i]];
            }
        }
        int newa = curposa + 1;
        int newb = curposb + 1;

        return result + min(dp(newa,curposb,1),dp(curposa,newb,0));
    }

}

int main(){
  cin >> N >> M;
  A.resize(N);
  S.resize(N);
  P.resize(N);
  suma.resize(N);
  B.resize(M); T.resize(M); Q.resize(M); sumb.resize(M);
  for(int i = 0;i< N;i++){
    cin >> A[i].val >> S[i] >> P[i];
    sum += A[i].val;
    total += P[i];
    suma[i] = sum;
  }
  sum = 0;
  for(int i = 0;i< M;i++){
    cin >> B[i].val >> T[i] >> Q[i];
    sum += B[i].val;
    total += Q[i];
    sumb[i] = sum;
  }
  for(int i = 0;i<N;i++){
    if(suma[i]  > S[i]){ P[i] = 0;}
    else{
       int lim = Up(B,S[i] - suma[i]);
       if(lim >= 0){
            if(B[lim].lis.size() == 0){
                lima.push_back(lim);
            }
            B[lim].lis.push_back(i);
       }
    }
  }

  for(int i = 0;i<M;i++){
    if(sumb[i] > T[i]){ Q[i] = 0;}
    else{
       int lim = Up(A,S[i] - suma[i]);
       if(lim >= 0){
            if(A[lim].lis.size() == 0){
                limb.push_back(lim);
            }
            A[lim].lis.push_back(i);
       }
    }
  }
  /*for(int i = 0;i< lima.size();i++){
    cout << lima[i] << " : ";
    for(int i1 = 0;i1<B[lima[i]].lis.size();i1++){
        cout << B[lima[i]].lis[i1] << " ";
    }
    cout << endl;
  }
  cout << endl;
  for(int i = 0;i< limb.size();i++){
    cout << limb[i] << " : ";
    for(int i1 = 0;i1<A[limb[i]].lis.size();i1++){
        cout << A[limb[i]].lis[i1] << " ";
    }
    cout << endl;
  }*/
  sort(lima.begin(),lima.end());
  sort(limb.begin(),limb.end());

  cout << total - min(dp(0,-1,1),dp(-1,0,0));
}

Compilation message (stderr)

dishes.cpp: In function 'int Up(const std::vector<c>&, int)':
dishes.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<AS.size();i++){
                   ~^~~~~~~~~~
dishes.cpp: In function 'int dp(const int&, const int&, const short int&)':
dishes.cpp:40:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0;i<B[pos1].lis.size();i++){
                           ~^~~~~~~~~~~~~~~~~~~
dishes.cpp:47:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0;i<A[pos1].lis.size();i++){
                           ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9