QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234372#5044. HappinessCSU2023#RE 84ms3948kbC++143.5kb2023-11-01 16:40:042023-11-01 16:40:04

Judging History

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

  • [2023-11-01 16:40:04]
  • 评测
  • 测评结果:RE
  • 用时:84ms
  • 内存:3948kb
  • [2023-11-01 16:40:04]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define mk make_pair
#define pii std::pair<int,int>
#define fi first
#define se second
const int N = 305;
const int M = 11;
const int INF = 1e9;
using std::cin;
using std::cout;
using std::ios;
using std::max;
using std::min;
using std::vector;
int n,m,F,L;
pii a[N][N],b[N][N];
int fir[N],las[N];
int dirt[N];
int sum[N];
int rk[N],p[N];
vector <int> t1,t2[N];
inline int read(){
	int v = 0,c = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') return -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		v = v * 10 + ch - 48;
		ch = getchar();
	}
	return v * c;
}
inline bool cmpl(int x,int y){
//	vector <int> t1,t2;
//	
//	for(int i = 1;i <= 10;++i){
//		if(b[x][i].fi != -1) t1.push_back(b[x][i].fi);
//		if(b[y][i].fi != -1) t2.push_back(b[y][i].fi); 
//	}
//	sort(t1.begin(),t1.end());
//	sort(t2.begin(),t2.end());
	if(x == n){
		for(int i = 0;i < (int)t1.size();++i){
			if(t1[i] < t2[y][i]) return 1;
			if(t1[i] > t2[y][i]) return 0;	
		}
		return 1;
	}
	else{
		assert(t2[x].size() == t2[y].size());
		for(int i = 0;i < (int)t2[x].size();++i){
			if(t2[x][i] < t2[y][i]) return 1;
			if(t2[x][i] > t2[y][i]) return 0;
		}
		return 1;
	}
}
inline bool cmp(int x,int y){
	return sum[x] > sum[y] || (sum[x] == sum[y] && dirt[x] < dirt[y]) || 
	(sum[x] == sum[y] && dirt[x] == dirt[y] && cmpl(x,y));
}
inline int work(){
	int now = 0,s = 0,d = 0;
	for(int i = 1;i <= 10;++i) b[n][i].fi = -1;
	for(int i = 1;i <= 10;++i){
		if(a[n][p[i]].fi == -1) continue;
		if(now + a[n][p[i]].fi <= 300){
			now += a[n][p[i]].fi;
			s++;d += now + a[n][p[i]].se * 20;
			b[n][p[i]].fi = now;
			b[n][p[i]].se = a[n][p[i]].se;
		}
		else break;
	}
	sum[n] = s,dirt[n] = d;
	
	t1.clear();
	for(int i = 1;i <= 10;++i){
		if(b[n][i].fi != -1) t1.push_back(b[n][i].fi);
	}
	sort(t1.begin(),t1.end());
	
	int l = 1,r = n - 1,res = n;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(cmp(n,rk[mid])) res = mid,r = mid - 1;
		else l = mid + 1;	
	}
//	printf("case : %d %d %d\n",sum[n],dirt[n],res);
	int cnt = 5000 / res;
	if(res <= n / 10) cnt += 1200;
	else if(res <= n / 10 * 3) cnt += 800;
	else if(res <= n / 10 * 6) cnt += 400;
	int ff = INF,ll = -1;
	for(int i = 1;i <= 10;++i){
		if(b[n][i].fi == -1) continue;	
		if(b[n][i].fi <= fir[i]) cnt += 800;
		ff = min(ff,b[n][i].fi);
		ll = max(ll,b[n][i].fi);
	}
	if(ff != INF && ff <= F) cnt += 700;
	if(ll != -1 && ll >= L) cnt += 500;
	return cnt;
}
int main(){
	n = read();
	for(int i = 1;i <= 300;++i) fir[i] = INF, las[i] = -1,rk[i] = i,F = INF,L = -1;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= 10;++j){
			a[i][j].fi = read();
			if(a[i][j].fi == -1) continue;
			a[i][j].se = read();
			b[i][j] = a[i][j];
			if(i == n) continue;
			dirt[i] += a[i][j].fi + a[i][j].se * 20;
			sum[i]++;
			fir[j] = min(fir[j],a[i][j].fi);
			las[j] = max(las[j],a[i][j].fi);
		//	printf("%d %d\n",a[i][j].fi,a[i][j].se);	
		}
	}
	for(int j = 1;j < n;++j){
		for(int i = 1;i <= 10;++i){
			F = min(F,fir[i]),L = max(L,las[i]);
			if(b[j][i].fi != -1) t2[j].push_back(b[j][i].fi);
		}
		sort(t2[j].begin(),t2[j].end());
		//,cout << fir[i] << " " << las[i] << "\n";
	}
	
	int ans = 0;
	std::sort(rk + 1,rk + n,cmp);
//	for(int i = 1;i < n;++i) cout << rk[i] << " ";
//	cout << "\n";
	for(int i = 1;i <= 10;++i) p[i] = i;
	do{
		ans = max(ans,work());
	}while(std::next_permutation(p + 1,p + 11));
	printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 84ms
memory: 3852kb

input:

10
233 1,-,-,7 7,257 4,173 5,117 1,-,-,85 3
-,231 0,167 0,257 7,-,-,122 4,283 0,215 4,-
41 1,-,290 8,-,-,-,-,246 7,120 3,184 9
142 8,243 7,69 0,-,41 9,-,279 1,264 4,-,74 9
53 8,-,187 9,60 1,48 8,99 10,-,-,55 7,259 5
250 0,-,-,-,166 0,16 3,-,82 4,73 0,184 3
-,-,-,-,105 3,-,-,-,152 4,-
-,84 5,98 8,-,1...

output:

1800

result:

ok 1 number(s): "1800"

Test #2:

score: 0
Accepted
time: 82ms
memory: 3948kb

input:

10
15 0,19 10,152 4,45 10,154 7,172 3,168 4,263 1,187 7,24 4
2 3,93 5,113 7,160 0,274 4,128 8,119 0,46 6,50 5,129 2
117 8,190 1,202 1,69 1,64 5,218 0,148 2,156 7,86 2,162 5
209 1,145 0,214 2,99 10,9 1,47 5,235 5,87 3,250 10,285 5
245 0,150 1,237 8,182 7,4 3,38 5,238 6,164 2,259 3,59 6
31 8,44 9,27 6...

output:

1300

result:

ok 1 number(s): "1300"

Test #3:

score: -100
Runtime Error

input:

300
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,...

output:


result: