QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#683321#9529. Farm Managementdoyo#WA 1ms5748kbC++201.1kb2024-10-27 20:11:452024-10-27 20:11:46

Judging History

你现在查看的是最新测评结果

  • [2024-10-27 20:11:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5748kb
  • [2024-10-27 20:11:45]
  • 提交

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]>lft) 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: 0ms
memory: 5664kb

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: 5748kb

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'