/ Randle /

记录详情

Memory Exceeded

/in/foo.cc: In function 'int main()':
/in/foo.cc:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(les.size()>k) {
       ~~~~~~~~~~^~
/in/foo.cc:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(les.size()>k) {
           ~~~~~~~~~~^~
# 状态 耗时 内存占用
#1 Accepted 3ms 324.0 KiB
#2 Accepted 2ms 452.0 KiB
#3 Accepted 2ms 456.0 KiB
#4 Accepted 35ms 2.566 MiB
#5 Accepted 18ms 1.441 MiB
#6 Time Exceeded ≥1006ms ≥130.301 MiB
#7 Memory Exceeded ≥435ms ≥256.0 MiB
#8 Memory Exceeded ≥495ms ≥256.0 MiB
#9 Memory Exceeded ≥509ms ≥256.0 MiB
#10 Memory Exceeded ≥475ms ≥256.0 MiB

代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#define maxn 100005
using namespace std;
int a[maxn],b[maxn],suma[maxn],sumb[maxn];double sub[maxn];
priority_queue<double,vector<double>,greater<double> > gr;
priority_queue<double,vector<double>,less<double> > les;
int main() {
	int n,k;
	cin>>n>>k;
	for(int i = 1; i<=n; i++) {
		scanf("%d",a+i);
		suma[i] = suma[i-1]+a[i];
	}
	for(int i = 1; i<=n; i++) {
		scanf("%d",b+i);
		sumb[i] = sumb[i-1]+b[i];
	}
	for(int i = 1;i<=n;i++){
		sub[i] = 1.0*a[i]/b[i];
	}
	if(k==1) {
		sort(sub+1,sub+1+n);
		printf("%.2lf",sub[n]);
		return 0;
	}
	for(int i = 1; i<=n; i++) {
		for(int j = 0; j<i; j++) {
			double toadd = -1.0*(suma[i]-suma[j])/(sumb[i]-sumb[j]);
			les.push(toadd);
			if(les.size()>k) {
				while(les.size()>k) {
					double t= les.top();
					les.pop();
					gr.push(t);
				}
			}
			if(!gr.empty()) {
				while(gr.top()<les.top()) {
					double t = gr.top();
					gr.pop();
					gr.push(les.top());
					les.pop();
					les.push(t);
				}
			}
		}
	}
	printf("%.2lf",-les.top());
	return 0;
}

信息

递交者
类型
递交
题目
梁山伯与祝英台(原创)
题目数据
下载
语言
C++
递交时间
2017-10-25 19:30:06
评测时间
2017-10-25 19:30:07
评测机
分数
50
总耗时
≥2985ms
峰值内存
≥256.0 MiB