QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234372 | #5044. Happiness | CSU2023# | RE | 84ms | 3948kb | C++14 | 3.5kb | 2023-11-01 16:40:04 | 2023-11-01 16:40:04 |
Judging History
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 -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,...