QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#888227#795. Cloud ComputingI_love_Riley_Andersen#0 596ms3712kbC++172.8kb2025-02-08 00:50:572025-02-08 00:50:58

Judging History

This is the latest submission verdict.

  • [2025-02-08 00:50:58]
  • Judged
  • Verdict: 0
  • Time: 596ms
  • Memory: 3712kb
  • [2025-02-08 00:50:57]
  • Submitted

answer

#include"bits/stdc++.h"
#include"ext/pb_ds/tree_policy.hpp"
#include"ext/pb_ds/assoc_container.hpp"
using namespace std;
using namespace __gnu_pbds;
#define FOR(i,a,b)for(int i=a;i<b;i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=b-1;a<=i;i--)
#define R0F(i,a)ROF(i,0,a)
#define rep(a)F0R(_,a)
#define each(a,x)for(auto&a:x)
#define all(a)begin(a),end(a)
#define sz(x)int(size(x))
#define lla(x)rbegin(x),rend(x)
#define SUM(a)accumulate(all(a),0ll)
#define SUMM(a,b)accumulate(a,a+b,0ll)
#define MAX(a)*max_element(all(a))
#define MAXX(a,b)*max_element(a,a+b)
#define MIN(a)*min_element(all(a))
#define MINN(a,b)*min_element(a,a+b)
#define con const int
#define lwb lower_bound
#define upb upper_bound
#define bry binary_search
#ifdef LOCAL
#define print(x)cout<<x;
#else
#define print(...)
#endif
#define debug(x)print(#x<<" = "<<x<<endl)
using ld=long double;
using ll=long long;
using str=string;
template<class T>using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>using omset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>T minn(T a){return a;}
template<class T,class...Args>T minn(T a,Args... args){return min(a,minn(args...));}
template<class T>T maxx(T a){return a;}
template<class T,class...Args>T maxx(T a,Args... args){return max(a,maxx(args...));}
#define SMIN(a,b...)a=min(a,minn(b))
#define SMAX(a,b...)a=max(a,maxx(b))
void fileset(str a){assert(nullptr!=freopen((a+".in").c_str(),"r",stdin)&&nullptr!=freopen((a+".out").c_str(),"w",stdout));}
con mxN = 2e3 + 3;

vector<tuple<int,int,int>> comps;
vector<tuple<int,int,int>> ordrs;

int dp[mxN][mxN];

int N, M;

int go(int i, int j){
    if (i == N || j == M) {
        return 0;
    }

    if (0 == dp[i][j]){
        auto& [c, f, v] = comps[i];
        auto& [C, F, V] = ordrs[j];

        if (f >= F){
            SMAX(dp[i][j], go(i + 1, j + 1) + V - v);
        }

        SMAX(dp[i][j], go(i + 1, j));
        SMAX(dp[i][j], go(i, j + 1));
    }

    return dp[i][j];
}

int main(){
    cin >> N;

    F0R (i, N){
        int c, f, v;
        cin >> c >> f >> v;

        comps.emplace_back(c, f, v);
    }

    cin >> M;

    F0R (i, M){
        int C, F, V;
        cin >> C >> F >> V;

        ordrs.emplace_back(C, F, V);
    }

    sort(all(comps),[](auto& i, auto& j){
        auto& [ci, fi, vi] = i;
        auto& [cj, fj, vj] = j;

        if (fi ^ fj){
            return fi < fj;
        } else {
            return vi < vj;
        }
    });

    sort(all(ordrs),[](auto& i, auto& j){
        auto& [ci, fi, vi] = i;
        auto& [cj, fj, vj] = j;

        if (fi ^ fj){
            return fi < fj;
        } else {
            return vi < vj;
        }
    });

    cout << go(0, 0) << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 18
Accepted
time: 1ms
memory: 3328kb

input:

1
3 3253 744
1
1 2012 798

output:

54

result:

ok single line: '54'

Test #2:

score: 18
Accepted
time: 1ms
memory: 3328kb

input:

1
1 2291 728
1
3 3024 858

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 3712kb

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:

39450

result:

wrong answer 1st lines differ - expected: '368159', found: '39450'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #18:

score: 18
Accepted
time: 1ms
memory: 3456kb

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:

23934

result:

ok single line: '23934'

Test #19:

score: 18
Accepted
time: 596ms
memory: 3584kb

input:

12
1 2208 8567
1 2221 8626
1 2152 8312
1 2293 8956
1 2261 8809
1 2062 7905
1 2203 8544
1 2105 8099
1 2280 8896
1 2057 7882
1 2015 7693
1 2162 8357
18
1 2563 10209
1 2000 7626
1 3072 12633
1 2789 11276
1 2144 8276
1 2921 11906
1 2380 9357
1 2077 7972
1 2103 8090
1 2868 11652
1 2684 10778
1 3043 12493...

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Time Limit Exceeded

input:

79
1 4427 4256458
1 3723 3490767
1 3982 3260428
1 3770 3355873
1 4741 4551396
1 5000 1319580
1 4063 2173424
1 2181 4525445
1 3737 1728963
1 3931 4866468
1 4157 4762822
1 4236 1841301
1 2378 2709820
1 4220 2261004
1 2446 4168561
1 4547 2573600
1 3060 2878656
1 4672 4605556
1 2852 3719524
1 4693 42886...

output:


result:


Subtask #4:

score: 0
Wrong Answer

Test #26:

score: 0
Wrong Answer
time: 0ms
memory: 3456kb

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:

11116

result:

wrong answer 1st lines differ - expected: '17705', found: '11116'

Subtask #5:

score: 0
Time Limit Exceeded

Test #34:

score: 18
Accepted
time: 0ms
memory: 3584kb

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
Time Limit Exceeded

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:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%