| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 115026 |
2019-06-04T15:42:57 Z |
Dung |
Two Dishes (JOI19_dishes) |
C++11 |
|
10000 ms |
32244 KB |
#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
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++){
~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10100 ms |
32244 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10100 ms |
32244 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10100 ms |
32244 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
