oj.uz

Submission #1034371

# Submission time Handle Problem Language Result Execution time Memory
1034371 2024-07-25T12:44:57 Z Phuoc Art Exhibition (JOI18_art) C++14
10 / 100
 4 ms 472 KB 
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <stack>
#include <queue>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define el '\n'
#define mpair make_pair
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define fi first
#define se second
 
/* Author: Pham Gia Phuoc */
 
const ll MOD = (ll)(1e9) + 1LL * 19972207;
 
template <class T1, class T2>
    void add(T1 &a, T2 b){
        a += b;
        if(a >= MOD) a -= MOD;
    }
 
template <class T1, class T2>
    void sub(T1 &a, T2 b){
        a -= b;
        if(a < 0) a += MOD;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if(a > b){a = b; return true;} return false;
    }
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if(a < b){a = b; return true;} return false;
    }
 
/** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/
 
const int MAX = 30010;
const ll INF = (ll) 1e18 + 67LL;
const int oo = (int)(1e9 + 7);
const int NUM_BIT = 62;

#define FOR(i, a, b) for(int i = a; i <= b; i++)

int n;
long long size[MAX], values[MAX];

void init(){
    cin >> n;
    FOR(i, 1, n) cin >> size[i] >> values[i];
}

namespace subtask1{
    bool check(){
        return n <= 16;
    }

    void solve(){
        long long ans = -INF;
        FOR(mask, 1, MASK(n) - 1){
            long long sumVal = 0, maxSize = 0, minSize = INF;
            FOR(i, 0, n - 1) if(BIT(mask, i))
                {sumVal += values[i + 1]; maximize(maxSize, size[i + 1]); minimize(minSize, size[i + 1]);}
            maximize(ans, sumVal - (maxSize - minSize));          
        }
        cout << ans;
    }
}

// namespace subtask2{
//     bool check(){
//         return n <= 300;
//     }

//     const int MAX_N = 310;
//     long long dp[MAX_N][MAX_N][MAX_N];

//     ll Try(int i, int j, int k){
//         if(i == 1) return values[1];
        
//     }

//     void solve(){
//         dp[1][1][1] = values[1];

//     }   
// }

void solve(){
    if(subtask1::check()){subtask1::solve(); return;}
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    while(t--){
        // gen();
        init();
        solve();
    }
    
    return 0;
}
 
 
 
/*** ROAD TO VOI 2025 ***/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 472 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 4 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 472 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 472 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 472 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -