QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#409423 | #795. Cloud Computing | Feet_McYeet | 0 | 47ms | 51892kb | C++17 | 3.4kb | 2024-05-12 03:19:15 | 2024-05-12 03:19:15 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <bitset>
// #include <bit>
// #pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define forn(i, n) for (int i = 0; i<n; i++)
#define forl(i, a, b) for (int i = a; i<b; i++)
#define spc << ' '
#define el << '\n'
#define nl cout << '\n'
#define pb push_back
#define sz size
#define fi first
#define se second
#define rsz resize
#define all(x) x.begin(), x.end()
const int inf = 1e9;
const ll inf2 = 1e18;
const int MAXN = 2005;
const int MAXC = 55;
struct cmp {
int c, f, v;
};
bool operator < (const cmp& c1, const cmp& c2) {
return c1.f<c2.f;
}
bool smax(ll& l1, const ll& l2) {
if (l2>l1) {
l1 = l2; return true;
}
return false;
}
int main() {
cin.tie(NULL); ios_base::sync_with_stdio(false);
int n; cin >> n;
cmp a[n];
forn(i,n) cin >> a[i].c >> a[i].f >> a[i].v;
int m; cin >> m;
cmp b[m];
forn(i,m) cin >> b[i].c >> b[i].f >> b[i].v;
sort(a,a+n);
sort(b,b+m);
ll dp[m+1][MAXC];
pair<pair<short, short>, short> o[m+1][MAXC];
vector<pair<int, short>> cl[m+1][MAXC+1];
bitset<MAXN> u[m+1][MAXC];
int p2 = n-1;
forn(i,m+1) forn(j,MAXC) {
dp[i][j] = -inf2;
o[i][j] = {{0, 0}, n};
u[i][j].reset();
}
dp[m][0] = 0;
for (int i = m-1; i>=0; i--) {
forn(j,MAXC) {
cl[i][j+1] = cl[i+1][j+1];
// if (i<m-1) {
// dp[i+1][j];
// u[i+1][j] = u[o[i+1][j].fi.fi][o[i+1][j].fi.se];
// u[i+1][j][o[i+1][j].se]=1;
// }
}
cmp cc = b[i];
for (; p2>=0 && a[p2].f >= cc.f; p2--) {
auto p = lower_bound(all(cl[i][a[p2].c]), make_pair(a[p2].v, (short) p2));
cl[i][a[p2].c].insert(p, {a[p2].v, p2});
}
forn(j, MAXC) {
u[i+1][j] = u[o[i+1][j].fi.fi][o[i+1][j].fi.se];
u[i+1][j][o[i+1][j].se]=1;
if (j >= cc.c) {
if (smax(dp[i][j-cc.c], dp[i+1][j] + cc.v)) {
o[i][j-cc.c] = {{i+1, j}, n};
}
}
else {
forl(k, 1, MAXC+1) {
for (auto l : cl[i][k]) {
if (!u[i+1][j][l.se]) {
if (j+k < MAXC) {
if (smax(dp[i+1][j+k], dp[i+1][j]-l.fi)) {
o[i+1][j+k] = {{i+1, j}, l.se};
}
}
else {
if (smax(dp[i][j+k-cc.c], dp[i+1][j]-l.fi+cc.v)) {
o[i][j+k-cc.c] = {{i+1, j}, l.se};
}
}
break;
}
}
}
}
if (smax(dp[i][j], dp[i+1][j])) o[i][j] = {{i+1, j}, n};
}
}
// forn(i,m+1) {
// forn(j, 12) {
// if (dp[i][j] > -100000) cout << dp[i][j] spc;
// else cout << ". ";
// }
// nl;
// }
// nl;
cout << *max_element(dp[0], dp[0]+MAXC) << endl;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 18
Accepted
time: 1ms
memory: 3588kb
input:
1 3 3253 744 1 1 2012 798
output:
54
result:
ok single line: '54'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1 1 2291 728 1 3 3024 858
output:
0
result:
ok single line: '0'
Test #3:
score: -18
Wrong Answer
time: 2ms
memory: 5244kb
input:
8 18 5754 6872 11 5543 1464 6 6940 9405 10 5152 4196 13 5784 7499 18 6787 260 14 5922 218 17 5037 7983 100 3 5482 4812 1 3922 7167 3 3566 8041 2 3532 3839 3 3948 4490 2 5301 6616 3 4216 796 2 4583 5021 1 3311 3984 3 3044 2702 2 4529 288 2 3352 6474 2 3102 4548 3 3784 2968 2 5054 2143 2 5385 1542 3 3...
output:
330848
result:
wrong answer 1st lines differ - expected: '368159', found: '330848'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 1ms
memory: 3856kb
input:
12 1 3728 3883 1 2483 1377 1 2421 2213 1 4866 648 1 2292 1737 1 4027 657 1 2119 2801 1 2559 859 1 3859 3261 1 2908 3110 1 2917 2467 1 2011 3406 18 1 2558 4956 1 3468 2947 1 4577 4082 1 2886 2222 1 2979 3572 1 2266 4860 1 2868 3183 1 3665 4259 1 2607 4802 1 2811 3874 1 2314 4212 1 2638 3152 1 2944 44...
output:
23099
result:
wrong answer 1st lines differ - expected: '23934', found: '23099'
Subtask #4:
score: 0
Wrong Answer
Test #26:
score: 18
Accepted
time: 1ms
memory: 3672kb
input:
10 2 1 2274 2 1 2524 1 1 2699 5 1 2930 4 1 1802 2 1 2734 4 1 1036 3 1 2741 5 1 1138 1 1 2132 6 5 1 3573 1 1 4847 2 1 3885 1 1 2183 2 1 2534 1 1 4659
output:
17705
result:
ok single line: '17705'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
10 5 1 19 3 1 14 4 1 10 3 1 10 4 1 20 2 1 9 1 1 4 4 1 10 1 1 2 3 1 10 6 5 1 13 5 1 13 3 1 10 1 1 3 5 1 13 5 1 13
output:
4
result:
ok single line: '4'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
1500 5 1 766 1 1 925 5 1 545 5 1 916 1 1 747 3 1 981 2 1 794 1 1 853 4 1 745 2 1 539 4 1 611 3 1 730 2 1 995 4 1 663 1 1 667 4 1 615 3 1 813 3 1 750 2 1 917 3 1 568 1 1 602 1 1 792 1 1 774 5 1 860 5 1 834 1 1 946 2 1 567 3 1 770 3 1 750 5 1 752 4 1 718 3 1 987 2 1 977 4 1 838 2 1 642 4 1 558 4 1 878...
output:
0
result:
ok single line: '0'
Test #29:
score: -18
Wrong Answer
time: 13ms
memory: 32648kb
input:
13 20 1 9848 33 1 11113 33 1 11397 43 1 5486 19 1 10018 37 1 8534 43 1 7616 43 1 5394 13 1 11453 44 1 11120 29 1 11057 46 1 9023 20 1 11984 1805 9 1 845 4 1 355 6 1 818 7 1 307 9 1 354 9 1 593 10 1 650 3 1 962 5 1 273 8 1 873 1 1 420 7 1 948 4 1 668 1 1 708 6 1 616 7 1 594 9 1 201 7 1 768 3 1 802 7 ...
output:
88315
result:
wrong answer 1st lines differ - expected: '102484', found: '88315'
Subtask #5:
score: 0
Wrong Answer
Test #34:
score: 18
Accepted
time: 1ms
memory: 3608kb
input:
4 43 2536 1 48 2001 1 49 3407 1 48 3778 1 2 42 3314 1 43 3073 1
output:
0
result:
ok single line: '0'
Test #35:
score: 0
Accepted
time: 0ms
memory: 5224kb
input:
57 47 1212 1 42 1104 1 48 1247 1 44 1420 1 41 1428 1 46 1364 1 47 1245 1 40 1199 1 48 1027 1 49 1113 1 50 1439 1 45 1208 1 41 1231 1 41 1131 1 48 1080 1 43 1218 1 45 1145 1 44 1071 1 43 1393 1 47 1314 1 45 1306 1 47 1439 1 42 1124 1 49 1383 1 47 1175 1 45 1099 1 46 1378 1 45 1285 1 46 1323 1 41 1234...
output:
0
result:
ok single line: '0'
Test #36:
score: 0
Accepted
time: 0ms
memory: 8356kb
input:
570 46 5838 1 40 6425 1 44 5897 1 42 6694 1 49 4775 1 43 6145 1 49 3903 1 46 4661 1 50 5987 1 43 7469 1 40 8641 1 47 7424 1 43 6303 1 44 9446 1 42 9626 1 48 3201 1 46 4829 1 44 7695 1 41 8599 1 48 4502 1 43 7551 1 44 4095 1 50 7648 1 45 5950 1 50 8967 1 42 3801 1 45 4723 1 42 8216 1 47 9791 1 41 586...
output:
233
result:
ok single line: '233'
Test #37:
score: 0
Accepted
time: 7ms
memory: 29804kb
input:
800 2 33219 1 3 24476 1 3 44557 1 1 84514 1 4 14659 1 1 62141 1 1 28408 1 3 26361 1 2 60406 1 4 75765 1 2 82764 1 4 57798 1 3 40248 1 3 41219 1 4 36238 1 1 59815 1 1 11587 1 2 25934 1 2 47903 1 2 33165 1 4 53043 1 1 78402 1 3 67224 1 2 43672 1 2 56655 1 2 30009 1 1 31863 1 2 98445 1 1 70192 1 3 3927...
output:
381
result:
ok single line: '381'
Test #38:
score: -18
Wrong Answer
time: 47ms
memory: 51892kb
input:
1968 48 775828552 1 49 129659926 1 43 782523018 1 42 716703760 1 46 788642039 1 43 512170994 1 46 129364119 1 48 201273594 1 43 65172168 1 49 396205350 1 46 603534679 1 40 689641431 1 44 492506422 1 43 325797549 1 42 852455369 1 42 269221916 1 44 30771715 1 41 591385973 1 44 921620444 1 40 722250199...
output:
104
result:
wrong answer 1st lines differ - expected: '119', found: '104'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%