이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define int long long
signed main(){
int n,m;
cin>>n>>m;
int arr1[n+1] = {0};
int arr2[m+1] = {0};
int a[n+1];int s[n+1];int p[n+1];
int b[m+1];int t[m+1];int q[m+1];
for(int i = 1;i<=n;i++){
cin>>a[i]>>s[i]>>p[i];
arr1[i] = a[i]+arr1[i-1];
}
for(int i = 1;i<=m;i++){
cin>>b[i]>>t[i]>>q[i];
arr2[i] = b[i]+arr2[i-1];
}
vector<pair<int,int>> lol[m+1];
for(int i = 1;i<=n;i++){
int l = 0 , r = m , ans = -1;
while(l<=r){
int mid = (l+r)/2;
if(arr2[mid]+arr1[i]<=s[i]){
ans = mid;l = mid+1;
}else r = mid-1;
}
if(ans==-1)continue;
lol[ans].push_back({i,p[i]});
}
long long all = 0;
for(int i = 1;i<=m;i++){
int l = 0 , r = n , ans = -1;
while(l<=r){
int mid = (l+r)/2;
if(arr2[i]+arr1[mid]<=t[i]){
ans = mid;l = mid+1;
}else r = mid-1;
}
if(ans==-1)continue;
lol[i-1].push_back({ans+1,-q[i]});
all+=q[i];
}
map<int,int> mp;
for(int i = 0;i<=m;i++){
for(auto j:lol[i]){
if(j.second>=0){
mp[j.first]+=j.second;
continue;
}
int ans = j.second;
auto it = mp.lower_bound(j.first);
while(it!=mp.end()){
if(ans+(*it).second>=0){
mp[(*it).first]+=ans;
ans = 0;
break;
}
ans+=(*it).second;
it = mp.erase(it);
}
}
}
for(auto i:mp)all+=i.second;
cout<<all<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |