Submission #1116877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116877		dosts	Cloud Computing (CEOI18_clo)	C++17	0 / 100	1 ms	348 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 = 2e18;
const int N = 1e3+50,Q = 2e5+50;

int add(int x,int y) {
    return ((x+y) >= MOD ? x+y-MOD : x+y);
}

int mult(int x,int y) {
    return ((x%MOD)*(y%MOD))%MOD;
}

int expo(int x,int y) {
    if (!y) return 1;
    int e = expo(x,y/2);
    e = mult(e,e);
    if (y&1) e = mult(e,x);
    return e;
}

int divide(int x,int y) {
    return mult(x,expo(y,MOD-2));
}

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;
    sort(computers.begin()+1,computers.end(),[&](const Computer& c1,const Computer& c2) {
        return c1.f > c2.f;
    });
    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;
    });
    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]);
    }
    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;
                ptr++;
            }
            //alcam
            while (ptr2 < bucket[i+1].size() && bucket[i+1][ptr2].c <= c+computers[i+1].c) {
                profittaken2 += bucket[i+1][ptr2].v;
                ptr2++;
            }
            dp[i+1][c] = max(dp[i+1][c],dp[i][c]+profittaken); 
            if (c+computers[i+1].c <= 50*n) {
            dp[i+1][c+computers[i+1].c] = max(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:81:24: 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 (ptr < bucket[i+1].size() && bucket[i+1][ptr].c <= c) {
      |                    ~~~~^~~~~~~~~~~~~~~~~~~~
clo.cpp:86:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Order>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             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