QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#409423#795. Cloud ComputingFeet_McYeet0 47ms51892kbC++173.4kb2024-05-12 03:19:152024-05-12 03:19:15

Judging History

This is the latest submission verdict.

  • [2024-05-12 03:19:15]
  • Judged
  • Verdict: 0
  • Time: 47ms
  • Memory: 51892kb
  • [2024-05-12 03:19:15]
  • Submitted

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%