oj.uz

Submission #1115265

# Submission time Handle Problem Language Result Execution time Memory
1115265 2024-11-20T09:39:58 Z staszic_ojuz Art Exhibition (JOI18_art) C++17
10 / 100
 26 ms 504 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <unordered_map>

using namespace std;

typedef long long ll;

struct dzielo {
    ll s;
    ll v;
};

ll ile(vector<bool> uklad, vector<ll> sp, vector<dzielo> art) {
    vector<dzielo> jakie;
    ll i0 = -1, i1 = -1;
    for(int i = 0; i < art.size(); i++) {
        if(uklad[i]) {
            if(i0 < 0) {i0 = i;}
            jakie.push_back(art[i]);
            i1 = i;
        }
    }
    //cout << i1 << " " << i0 << " " <<sp[i1 + 1] << " " << sp[i0] << " " << art[i1].s << " " << art[i0].s << '\n';
    return (sp[i1 + 1] - sp[i0] - art[i1].s + art[i0].s);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n; cin >> n;
    vector<dzielo> arts(n);
    for(int i = 0; i < n; i++) {
        ll s, v; cin >> s >> v;
        arts[i].s = s; arts[i].v = v;
    }
    sort(arts.begin(), arts.end(), [](dzielo a, dzielo b) {return a.s < b.s;});

    vector<ll> diff(n - 1);
    for(int i = 0; i < n - 1; i++) {
        diff[i] = arts[i - 1].s - arts[i].s;
    }
    vector<ll> sp(n + 1, 0);
    for(int i = 0; i < n; i++) {
        sp[i + 1] = sp[i] + arts[i].v;
        //cout << sp[i + 1] << " ";
    }
    //cout << endl;
    
    ll mx = 0;
    for(ll i = 1; i < (1<<n); i++) {
        vector<bool> c(n);
        for(int j = 0; j < n; j++) {
            c[j] = (i & (1<<j)) > 0;
            //cout << c[j];
        }
        //cout << " " << ile(c, sp, arts) << endl;
        
        mx = max(mx, ile(c, sp, arts));
    }

    cout << mx;

    return 0;
    
}

Compilation message

art.cpp: In function 'll ile(std::vector<bool>, std::vector<long long int>, std::vector<dzielo>)':
art.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<dzielo>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0; i < art.size(); i++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 336 KB Output is correct
2 Correct 25 ms 336 KB Output is correct
3 Correct 20 ms 336 KB Output is correct
4 Correct 23 ms 336 KB Output is correct
5 Correct 20 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 21 ms 336 KB Output is correct
9 Correct 20 ms 336 KB Output is correct
10 Correct 20 ms 336 KB Output is correct
11 Correct 26 ms 336 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 336 KB Output is correct
2 Correct 25 ms 336 KB Output is correct
3 Correct 20 ms 336 KB Output is correct
4 Correct 23 ms 336 KB Output is correct
5 Correct 20 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 21 ms 336 KB Output is correct
9 Correct 20 ms 336 KB Output is correct
10 Correct 20 ms 336 KB Output is correct
11 Correct 26 ms 336 KB Output is correct
12 Incorrect 9 ms 504 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 336 KB Output is correct
2 Correct 25 ms 336 KB Output is correct
3 Correct 20 ms 336 KB Output is correct
4 Correct 23 ms 336 KB Output is correct
5 Correct 20 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 21 ms 336 KB Output is correct
9 Correct 20 ms 336 KB Output is correct
10 Correct 20 ms 336 KB Output is correct
11 Correct 26 ms 336 KB Output is correct
12 Incorrect 9 ms 504 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 336 KB Output is correct
2 Correct 25 ms 336 KB Output is correct
3 Correct 20 ms 336 KB Output is correct
4 Correct 23 ms 336 KB Output is correct
5 Correct 20 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 21 ms 336 KB Output is correct
9 Correct 20 ms 336 KB Output is correct
10 Correct 20 ms 336 KB Output is correct
11 Correct 26 ms 336 KB Output is correct
12 Incorrect 9 ms 504 KB Output isn't correct
13 Halted 0 ms 0 KB -