oj.uz

Submission #525792

# Submission time Handle Problem Language Result Execution time Memory
525792 2022-02-12T22:31:55 Z ali22413836 Olympiads (BOI19_olympiads) C++14
100 / 100
 1400 ms 1896 KB 
#include <bits/stdc++.h>
#define  endl "\n"
using namespace std ;
typedef int ll;
typedef long double ld ;
//ll mypower(ll x, ll y){
//    if(y == 0) return 1 ;
//    if(y == 1) return x ;
//    ll ret = mypower(x , y / 2);
//    ret = (ret * ret) % mod;
//    if(y % 2) ret = ( ret * x ) % mod ;
//    return ret ;
//}
ll n , k , c ;
ll a[509][509] ;
set < pair < ll , vector < ll > > > ss;
bool can(ll ind , vector < ll > x){
    for(auto p : x){
        if (p == ind)
            return 0 ;
    }
    return 1 ;
}
vector < ll > ans ;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k >> c ;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= k ; j++){
            cin >> a[i][j] ;
        }
    }
    ss.insert({0 , {}}) ;
    for(int i = 1 ; i <= k ; i++){
        set < pair < ll , vector < ll > > > ss2 ;
        for(auto p : ss){
            for(int j = 1 ; j <= n ; j++){
                if(can(j , p.second)){
                    vector < ll > nv = p.second ;
                    nv.push_back(j) ;
                    sort(nv.begin() , nv.end()) ;
                    ll nco = 0 ;
                    for(int l = 1 ; l <= nv.size() ; l++){
                        ll mx = 0 ;
                        for(auto q : nv){
                            mx = max(mx , a[q][l]) ;
                        }
                        nco += mx ;
                    }
                    ss2.insert({nco , nv}) ;
                }
            }
            while(ss2.size() > c + 200){
                ss2.erase(ss2.begin()) ;
            }
        }
        ss = ss2 ;
    }
    for(auto p : ss)
        ans.push_back(p.first);
    cout << ans[ans.size() - c] << endl ;
    return 0 ;
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:43:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                     for(int l = 1 ; l <= nv.size() ; l++){
      |                                     ~~^~~~~~~~~~~~
olympiads.cpp:53:30: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   53 |             while(ss2.size() > c + 200){
      |                   ~~~~~~~~~~~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1756 KB Output is correct
2 Correct 87 ms 1768 KB Output is correct
3 Correct 80 ms 1776 KB Output is correct
4 Correct 69 ms 1768 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 860 KB Output is correct
2 Correct 78 ms 856 KB Output is correct
3 Correct 77 ms 876 KB Output is correct
4 Correct 78 ms 860 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 1824 KB Output is correct
2 Correct 1347 ms 1828 KB Output is correct
3 Correct 1400 ms 1896 KB Output is correct
4 Correct 1400 ms 1824 KB Output is correct
5 Correct 1391 ms 1860 KB Output is correct
6 Correct 35 ms 716 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1756 KB Output is correct
2 Correct 87 ms 1768 KB Output is correct
3 Correct 80 ms 1776 KB Output is correct
4 Correct 69 ms 1768 KB Output is correct
5 Correct 79 ms 860 KB Output is correct
6 Correct 78 ms 856 KB Output is correct
7 Correct 77 ms 876 KB Output is correct
8 Correct 78 ms 860 KB Output is correct
9 Correct 1345 ms 1824 KB Output is correct
10 Correct 1347 ms 1828 KB Output is correct
11 Correct 1400 ms 1896 KB Output is correct
12 Correct 1400 ms 1824 KB Output is correct
13 Correct 1391 ms 1860 KB Output is correct
14 Correct 35 ms 716 KB Output is correct
15 Correct 1392 ms 1824 KB Output is correct
16 Correct 1358 ms 1828 KB Output is correct
17 Correct 1350 ms 1824 KB Output is correct
18 Correct 1383 ms 1828 KB Output is correct
19 Correct 1341 ms 1828 KB Output is correct