QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300902 | #5044. Happiness | Saanteye | WA | 207ms | 3652kb | C++17 | 4.9kb | 2024-01-08 23:54:11 | 2024-01-08 23:54:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> PII;
//#define p first
//#define d second
void solve(){
int n; cin >> n;
vector<string> s(n);
getchar();
for (int i = 0; i < n; i++) {
getline(cin,s[i]);
}
vector<vector<int>> sv(n, vector<int> (10));
vector<vector<int>> pl(n, vector<int> (10));
vector<int> ac(n),ple(n);
for (int i = 0; i < n; i++) {
int tim = 0,fs = -1, cnt = 0;
for (auto c:s[i]) {
if (c == '\n') continue;
else if (c == ' ') fs = 0;
else if (c >= '0' && c <= '9') {
if (fs != -1) fs = fs * 10 + c - '0';
else tim = tim * 10 + c - '0';
}
else if (c == ',') {
sv[i][cnt] = tim; pl[i][cnt] = fs;
if (fs == -1) sv[i][cnt] = 1e18;
cnt++; tim = 0; fs = -1;
}
}
sv[i][cnt] = tim; pl[i][cnt] = fs;
if (fs == -1) sv[i][cnt] = 1e18;
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < 10; j++) {
// if (pl[i][j] == -1) cout << "- ";
// else
// cout << pl[i][j] << ' ';
// }
// cout << '\n';
// }
//for (int i = 0; i < n; i++)
// cout << sv[i][0] << '\n';
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < 10; j++)
if (sv[i][j] != 1e18)
ac[i]++, ple[i] = pl[i][j] * 20;
//mi,mx,fb
int mi = 1e18, mx = -1e18;
vector<int> fb(10,1e18);
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < 10; j++) {
if (sv[i][j] == 1e18) continue;
fb[j] = min(fb[j],sv[i][j]);
mi = min(mi, sv[i][j]);
mx = max(mx, sv[i][j]);
}
sort(sv[i].begin(), sv[i].end());
}
vector<int> rk(n),rrk(n);
for (int i = 0; i < n; i++) rk[i] = i;
sort(rk.begin(), rk.end() - 1,[&](int a,int b){
if (ac[a] != ac[b]) return ac[a] > ac[b];
if (ple[a] != ple[b]) return ple[a] < ple[b];
for (int i = 0; i < 10; i++)
if (sv[a][i] != sv[b][i])
return sv[a][i] < sv[b][i];
return false;
});
for (int i = 0; i < n; i++) {
rrk[rk[i]] = i;
}
// for (int i = 0; i < 10; i++)
// cout << fb[i] << ' ';
// return;
vector<int> ord(10);
iota(ord.begin(), ord.end(),0);
int ans = 0;
ac[n - 1] = -1e18; ple[n - 1] = 1e18;
do {
int now = 0, hap = 0;
int ov1 = 0, ove = 0;
vector<int> svl(10,1e18);
int rac = 0, rple = 0;
for (int i = 0; i < 10; i++) {
if (sv[n - 1][ord[i]] == 1e18) continue;
int rsv = sv[n - 1][ord[i]] + now;
now = rsv;
if (now > 300) continue;
rple += rsv + pl[n - 1][ord[i]];
rac += 1;
if (rsv <= fb[ord[i]]) hap += 800;
if (rsv <= mi) ov1 = 1;
if (rsv >= mx) ove = 1;
svl[i] = rsv;
}
if (ov1) hap += 700;
if (ove) hap += 500;
int l = -1, r = n;
while (r - l > 1) {
int mid = (r + l) >> 1;
int idx = rrk[mid];
if (ac[idx] != rac) {
if (ac[idx] > rac) l = mid;
else r = mid;
continue;
} else if (ple[idx] != rple) {
if (ple[idx] < rple) l = mid;
else r = mid;
continue;
} else {
int f = 0;
for (int i = 0; i < 10; i++)
if (sv[idx][i] != svl[i]) {
if (sv[idx][i] > svl[i]) r = mid;
else l = mid;
f = 1;
break;
}
if (!f) r = mid;
continue;
}
}
r += 1;
// cout << rac << ' ' << rple << '\n';
hap += 5000 / r;
if (r <= n / 10) hap += 1200;
else if (r <= n / 10 * 3) hap += 800;
else if (r <= n / 10 * 6) hap += 400;
ans = max(ans, hap);
} while (next_permutation(ord.begin(),ord.end()));
cout << ans;
}
//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,-,120 8,241 3,94 1,-,28 7,109 8
//280 6,246 5,58 9,-,-,-,-,-,-,-
//38 10,-,227 10,187 9,182 1,-,203 9,254 7,-,-
signed main(){
// ios::sync_with_stdio(false);
// srand(time(0));
int _ = 1;
//cin >> _;
while(_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 127ms
memory: 3432kb
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: 118ms
memory: 3472kb
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: 0
Accepted
time: 200ms
memory: 3652kb
input:
300 -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,...
output:
6200
result:
ok 1 number(s): "6200"
Test #4:
score: 0
Accepted
time: 178ms
memory: 3544kb
input:
300 164 7,180 10,59 4,162 10,16 3,140 1,204 10,73 9,289 5,14 8 97 3,18 1,153 4,160 6,166 10,25 8,300 9,183 8,98 10,195 10 195 5,247 10,116 1,129 7,79 5,238 7,198 3,192 2,282 7,117 2 125 1,269 10,188 9,72 8,65 5,249 5,46 1,192 3,77 0,241 3 18 1,147 0,12 6,34 9,120 3,282 4,44 1,206 2,50 10,125 10 174 ...
output:
16
result:
ok 1 number(s): "16"
Test #5:
score: 0
Accepted
time: 181ms
memory: 3608kb
input:
300 -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,...
output:
9800
result:
ok 1 number(s): "9800"
Test #6:
score: -100
Wrong Answer
time: 207ms
memory: 3552kb
input:
300 171 8,75 1,-,190 7,44 5,-,10 9,72 1,63 2,- 295 0,-,60 10,-,64 7,-,-,-,-,- 247 8,67 10,-,-,93 1,-,69 4,90 1,-,- 278 1,206 7,-,-,22 4,97 1,-,156 1,227 0,276 4 245 6,111 5,-,-,281 10,44 7,266 4,-,130 5,- 244 7,-,-,-,183 9,118 7,-,-,123 8,158 2 63 5,-,-,117 3,286 7,-,-,-,278 1,151 5 291 1,223 6,-,-,...
output:
22
result:
wrong answer 1st numbers differ - expected: '20', found: '22'