Submission #1115265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115265		staszic_ojuz	Art Exhibition (JOI18_art)	C++17	10 / 100	26 ms	504 KiB

art

#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 (stderr)

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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50