Submission #1116887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116887		dosts	Cloud Computing (CEOI18_clo)	C++17	0 / 100	2 ms	336 KiB

clo

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
int MOD = 1e9+7,inf = 1e18;
const int N = 1e3+50,Q = 2e5+50;


void mx(int& a,int b) {
    if (a < b) a = b;
    return;
}
void mn(int& a,int b) {
    if (a > b) a = b;
    return;
}

struct Order {
    int c,f,v;
};

struct Computer {
    int c,f,v;
};

void solve() {
    //dp[i][j] --> ilk i bilgisayarda j güç aldıysam ilk i bilgisayara izin verenlerden max profit
    //dp[i][j] --> dp[i+1][j] (+(i+1.bilgisayarı ilgilendirenlerden profit toplamı))
    //dp[i][j] --> dp[i+1][j+p[i+1]] (+(i+1.bilgisayarı ilgilendirenlerden profit toplamı) - v[i])
    //n * n * c --> two pointers
    int n;
    cin >>  n;
    vector<Computer> computers(n+1);
    for (int i=1;i<=n;i++) cin >> computers[i].c >> computers[i].f >> computers[i].v;
    int m;
    cin >> m;
    vector<Order> order(m+1);
    for (int i=1;i<=m;i++) cin >> order[i].c >> order[i].f >> order[i].v;
    sort(order.begin()+1,order.end(),[&](const Order& o1,const Order& o2) {
        return o1.f > o2.f;
    });
    sort(computers.begin()+1,computers.end(),[&](const Computer& c1,const Computer& c2) {
        return c1.f > c2.f;
    });
    vector<Order> bucket[n+1];
    int ptr = 0;
    for (int i=1;i<=m;i++) {
        while (ptr<n && computers[ptr+1].f >= order[i].f) ptr++;
        bucket[ptr].push_back(order[i]);
    }
    for (int i=1;i<=n;i++) {
        if (bucket[i].empty()) continue;
        sort(bucket[i].begin()+1,bucket[i].end(),[&](const Order& o1,const Order& o2) {
        return o1.c < o2.c;
        });
    }
    int dp[n+1][50*n+1];
    for (int i=0;i<=n;i++) {
        for (int j = 0;j<=50*n;j++) dp[i][j] = -inf;
    }
    dp[0][0] = 0;
    for (int i=0;i<n;i++) {
        int ptr = 0;
        int ptr2 = 0;
        int profittaken = 0;
        int profittaken2 = 0;
        for (int c = 0;c <= 50*n;c++) {
            if (dp[i][c] == -inf) continue;
            //almicam
            while (ptr < bucket[i+1].size() && bucket[i+1][ptr].c <= c) {
                profittaken += bucket[i+1][ptr++].v;
            }
            //alcam
            while (ptr2 < bucket[i+1].size() && bucket[i+1][ptr2].c <= c+computers[i+1].c) {
                profittaken2 += bucket[i+1][ptr2++].v;
            }
            mx(dp[i+1][c],dp[i][c]+profittaken); 
            if (c+computers[i+1].c <= 50*n) {
            mx(dp[i+1][c+computers[i+1].c],dp[i][c]-computers[i+1].v+profittaken2); 
            }
        }
    }
    int ans = 0;
    for (int i=0;i<=50*n;i++) ans = max(ans,dp[n][i]);
    cout << ans << '\n';
}                    
                             
int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message (stderr)

clo.cpp: In function 'void solve()':
clo.cpp:77:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Order>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             while (ptr < bucket[i+1].size() && bucket[i+1][ptr].c <= c) {
      |                    ~~~~^~~~~~~~~~~~~~~~~~~~
clo.cpp:81:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Order>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             while (ptr2 < bucket[i+1].size() && bucket[i+1][ptr2].c <= c+computers[i+1].c) {
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~

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