Submission #484458

#	Time	Username	Problem	Language	Result	Execution time	Memory
484458		ArianKheirandish	Cloud Computing (CEOI18_clo)	C++14	100 / 100	2043 ms	3688 KiB

clo

#include <bits/stdc++.h>
using namespace std;

#define ios                ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define mp                make_pair
#define bug(str, x)            cerr << str << " : " << x << '\n'

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e3 + 1;
const int maxc = 50 + 1;
const int inf = 1e9 + 10;
const int mod = 1e9 + 7;

ll dp[2][maxn][2][maxc];
int c[maxn], f[maxn], v[maxn];
int C[maxn], F[maxn], V[maxn];
vector<pii> S1, S2;

int main(){
    ios;
    int n, m;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> c[i] >> f[i] >> v[i];
        S1.pb(mp(f[i], i));
    }
    sort(all(S1));
    cin >> m;
    for(int i = 1; i <= m; i ++){
        cin >> C[i] >> F[i] >> V[i];
        S2.pb(mp(F[i], i));
    }
    sort(all(S2));
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            int c1 = c[S1[i - 1].second];
            int c2 = C[S2[j - 1].second];
            int p1 = (i == 1 ? 0 : c[S1[i - 2].second]);
            int p2 = (j == 1 ? 0 : C[S2[j - 2].second]);
            for(int k = 0; k <= 1; k ++){
                int oth = !k ? c2 : c1;
                for(int u = 1; u <= oth; u ++){
                    dp[1][j][k][u] = 0;
                    if(!k or u == c1)
                        dp[1][j][k][u] = dp[0][j][0][k ? c2 : u];
                    if(k or u == c2)
                        dp[1][j][k][u] = max(dp[1][j][k][u], dp[1][j - 1][1][!k ? c1 : u]);
                    if(S1[i - 1].first >= S2[j - 1].first){
                        int t1, t2;
                        if(!k)
                            t1 = c1, t2 = u;
                        else
                            t1 = u, t2 = c2;
                        ll res1 = (t1 == c1 ? v[S1[i - 1].second] : 0);
                        ll res2 = (t2 <= t1 ? V[S2[j - 1].second] : 0);
                        ll tp;
                        if(t1 == t2){
                            tp = dp[0][j - 1][0][p2];
                        }
                        else if(t1 > t2){
                            tp = dp[1][j - 1][1][t1 - t2];
                        }
                        else{
                            tp = dp[0][j][0][t2 - t1];
                        }
                        tp += res2 - res1;
                        dp[1][j][k][u] = max(dp[1][j][k][u], tp);
                    }
                }
            }
        }
        swap(dp[0], dp[1]);
    }
    cout << dp[0][m][0][C[S2[m - 1].second]] << '\n';
}

Compilation message (stderr)

clo.cpp: In function 'int main()':
clo.cpp:41:17: warning: unused variable 'p1' [-Wunused-variable]
   41 |             int p1 = (i == 1 ? 0 : c[S1[i - 2].second]);
      |                 ^~

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10