QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#683332 | #9529. Farm Management | doyo# | WA | 1ms | 5680kb | C++20 | 1.1kb | 2024-10-27 20:17:00 | 2024-10-27 20:17:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;++i)
#define For(i,j,k) for(int i=j;i>=k;--i)
#define int long long
const int N = 2e5 + 111;
vector<int> e[N];
int busy[N];
int vis[N];
vector<int> ans[N];
int que[N];
struct u{
int w,l,r,len;
}s[N];
int suf[N];
int wsuf[N];
bool cmpw(u x,u y){return x.w<y.w;}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
FOR(i,1,n){
cin>>s[i].w>>s[i].l>>s[i].r;
s[i].len = s[i].r-s[i].l;
}
++n;
s[n].w = 0;
s[n].l = 0;
s[n].r = m;
s[n].len = s[n].r-s[n].l;
sort(s+1,s+1+n,cmpw);
int sum = 0;
int lft = m;
FOR(i,1,n){
lft-=s[i].l;
sum += s[i].l * s[i].w;
}
int ans = sum;
For(i,n,1){
suf[i] = suf[i+1] + s[i].len;
wsuf[i] = wsuf[i+1] + s[i].len*s[i].w;
}
FOR(i,1,n){
int l = i+1,r = n;
int mid = 0;
int nowlft = lft + s[i].l;
int nowsum = sum - s[i].w*s[i].l;
while(l<r){
mid = (l+r>>1);
if(suf[mid]>nowlft) l = mid+1;
else r = mid;
}
nowlft -= suf[l];
nowsum += wsuf[l] + nowlft*s[l-1].w;
ans = max(ans,nowsum);
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5636kb
input:
5 17 2 3 4 6 1 5 8 2 4 4 3 3 7 5 5
output:
109
result:
ok single line: '109'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5680kb
input:
12 62 503792 9 10 607358 1 3 600501 10 10 33249 4 4 774438 6 6 197692 3 6 495807 8 8 790225 5 9 77272 3 8 494819 4 9 894779 3 9 306279 5 6
output:
35309054
result:
wrong answer 1st lines differ - expected: '35204500', found: '35309054'