oj.uz

Submission #1103712

# Submission time Handle Problem Language Result Execution time Memory
1103712 2024-10-21T14:49:53 Z khoile25108 Cloud Computing (CEOI18_clo) C++14
18 / 100
 686 ms 1876 KB 
#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define lcm(a,b) (a*b)/__gcd(a,b)
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 105;

const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const int dxx[] = {-1,-1,0,1,1,1,0,-1};
const int dyy[] = {0,1,1,1,0,-1,-1,-1};

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

bool cmp(dat a, dat b)
{
    return a.f != b.f ? a.f > b.f : a.v < b.v;
}

int n, sum, m;
vector<dat> a;
int dp[N][2];

void solve()
{
    sort(a.begin(), a.end(), cmp);
    FOR(i,1,sum)
        dp[i][0] = -INF;
    for(int i = 0; i < a.size(); i++)
    {
        for(int j = 0; j <= sum; j++)
            dp[j][1] = dp[j][0];
        for(int j = 0; j <= sum; j++)
        {
            int pre = j - a[i].c;
            if(pre >= 0 && pre <= sum)
                dp[j][1] = max(dp[j][1], dp[pre][0] + a[i].v);
        }
        for(int j = 0; j <= sum; j++)
            dp[j][0] = dp[j][1];
    }
    int ans = 0;
    FOR(i,1,sum)
        ans = max(ans, dp[i][0]);
    cout << ans;
}

void input()
{
    //freopen("TEST.INP", "r", stdin);
    //freopen("TEST.OUT", "w", stdout);
    cin >> n;
    FOR(i,1,n)
    {
        int c, f, v;
        cin >> c >> f >> v;
        a.pb({c,f,-v});
        sum += c;
    }
    cin >> m;
    FOR(i,1,m)
    {
        int c, f, v;
        cin >> c >> f >> v;
        a.pb({-c,f,v});
    }
}

signed main()
{
    faster
    input();
    solve();
}

Compilation message

clo.cpp: In function 'void solve()':
clo.cpp:46:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<dat>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i < a.size(); i++)
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 71 ms 916 KB Output is correct
4 Correct 9 ms 596 KB Output is correct
5 Correct 657 ms 1876 KB Output is correct
6 Correct 686 ms 1876 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -