QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#522010 | #5044. Happiness | JEdward | WA | 230ms | 3888kb | C++14 | 2.1kb | 2024-08-16 17:19:52 | 2024-08-16 17:19:53 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int,int>
#define all(s) s.begin(), s.end()
using namespace std;
int n;
auto read(){
string s; getline(cin, s);
array<pii, 10> res;
fill(all(res), make_pair(-1, -1));
for(int i=0,l=0;i<10;i++){
int r = l;
while(r < s.size() && (s[r] ^ ',')) ++r;
string real = s.substr(l, r-l);
if(real == "-") res[i] = {-1, -1};
else{
int m = real.find(' ');
res[i].first = stoll(real.substr(0, m)), res[i].second = stoll(real.substr(m+1));
}
l = r+1;
}
return res;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n; cin.get();
vector<array<pii, 10>> a(n-1);
vector<vector<int>> stand;
vector<int> first_solve(10, 300);
int fst = 300, lst = 0;
for(int i=0;i<n-1;i++){
a[i] = read();
int solved = 0, penalty = 0;
vector<int> v{0, 0};
for(int j=0;j<10;j++){
if(a[i][j].first==-1) continue;
++solved;
penalty += a[i][j].first + a[i][j].second * 20;
first_solve[j] = min(first_solve[j], a[i][j].first);
fst = min(fst, a[i][j].first);
lst = max(lst, a[i][j].first);
v.push_back(-a[i][j].first);
}
sort(v.begin() + 2, v.end());
v[0] = solved, v[1] = -penalty;
stand.push_back(v);
}
auto me = read();
vector<int> perm;
for(int i=0;i<10;i++) if(me[i].first != -1) perm.push_back(i);
int ans = 0;
do{
int solved = 0, penalty = 0, happiness = 0, time = 0;
vector<int> v{0, 0};
bool F = 0, L = 0;
for(int i=0;i<perm.size();i++){
int j = perm[i];
time += me[j].first;
if(time > 300) break;
++solved;
penalty += time + me[j].second * 20;
if(time <= fst) F = 1;
if(time >= lst) L = 1;
if(time <= first_solve[j]) happiness += 800;
v.push_back(-time);
}
if(F) happiness += 700;
if(L) happiness += 500;
sort(v.begin()+2, v.end());
v[0] = solved, v[1] = -penalty;
int rk = n - (upper_bound(all(stand), v) - stand.begin());
happiness += 5000 / rk;
if(rk <= n/10) happiness += 1200;
else if(rk <= n/10 * 3) happiness += 800;
else if(rk <= n/10 * 6) happiness += 400;
ans = max(ans, happiness);
} while(next_permutation(all(perm)));
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3888kb
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: 183ms
memory: 3592kb
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: 0ms
memory: 3700kb
input:
300 -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,...
output:
6200
result:
ok 1 number(s): "6200"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3652kb
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: 230ms
memory: 3736kb
input:
300 -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,...
output:
9800
result:
ok 1 number(s): "9800"
Test #6:
score: -100
Wrong Answer
time: 224ms
memory: 3704kb
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:
433
result:
wrong answer 1st numbers differ - expected: '20', found: '433'