| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 115218 |
2019-06-06T05:28:33 Z |
Dung |
Two Dishes (JOI19_dishes) |
C++11 |
|
10000 ms |
124280 KB |
#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));
}
Compilation message
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++){
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10061 ms |
124280 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
263 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
263 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
263 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
263 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
263 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10061 ms |
124280 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10061 ms |
124280 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
