제출 #115218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
115218		Dung	Two Dishes (JOI19_dishes)	C++11	0 / 100	10061 ms	124280 KiB

dishes

#include <bits/stdc++.h>
#include <iostream>
#include <map>
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;
map<int,vector<int> > changeA,changeB;

long 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& xa,const int& nxa,const int& xb,const int& nxb,map<int,vector<int> >::iterator curposa,map<int,vector<int> >::iterator curposb,const short& state,short state1,short state2){
    int result = 0;
    if(curposa == changeA.end() || curposb == changeB.end()){
        return 0;
    }
    else{
        if(state == 1){
            int pos = 0;
            if(state1 >= 0){pos = curposb != --(changeB.end()) && curposb != changeB.end() ? nxb - 1 : xb;}
            else{
                pos =xb - 1;
            }
            for(auto p : changeA[xa]){
                result += p <= pos ? 0 : P[p];
            }
        }
        else{
            int pos = 0;
            if(state2 >= 0){pos = curposa != --(changeA.end()) && curposa != changeA.end() ? nxa - 1 : xa;}
            else{
                pos = xa - 1;
            }
            for(auto p : changeB[xb]){
                result += p <= pos ? 0 : Q[p];
            }
        }
        map<int,vector<int> >::iterator newcurposa = curposa;
        map<int,vector<int> >::iterator newcurposb = curposb;
        if(state1 >= 0){++curposa;}
        if(state2 >= 0){++curposb;}
        return result + min(dp(curposa->first,0,newcurposb->first,curposb->first,curposa,newcurposb,1,state1 + 1,state2),dp(newcurposa->first,curposa->first,curposb->first,0,newcurposa,curposb,0,state1,state2 + 1));
    }

}

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 = upper_bound(sumb.begin(),sumb.end(),S[i] - suma[i]) - sumb.begin();
       changeA[lim].push_back(i);
    }
  }

  for(int i = 0;i<M;i++){
    if(sumb[i] > T[i]){ Q[i] = 0;}
    else{
       int lim = upper_bound(suma.begin(),suma.end(),T[i] - sumb[i]) - sumb.begin();
       changeB[lim].push_back(i);
    }
  }
  cout << total - min(dp(changeA.begin()->first,0,changeB.begin()->first,(++changeB.begin())->first,changeA.begin(),changeB.begin(),1,0,-1),dp(changeA.begin()->first,(++changeA.begin())->first,changeB.begin()->first,0,changeA.begin(),changeB.begin(),0,-1,0));
}

컴파일 시 표준 에러 (stderr) 메시지

dishes.cpp: In function 'int Up(const std::vector<c>&, int)':
dishes.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<AS.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