oj.uz

Submission #525503

# Submission time Handle Problem Language Result Execution time Memory
525503 2022-02-11T19:34:11 Z Yazan_Alattar Olympiads (BOI19_olympiads) C++14
100 / 100
 1581 ms 1920 KB 
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define F first
    #define S second
    #define pb push_back
    //#define endl "\n"
    #define all(x) x.begin(), x.end()
    const int M = 507;
    const ll inf = 1e9;
    const ll mod = 998244353;
    const double pi = acos(-1);
    const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
     
    int n, k, c, a[M][M];
     
    bool valid (vector <int> v, int person) {
    	for(auto i : v) if(person == i) return 0;
    	return 1;
    }
     
    int val (vector <int> v) {
    	int ret = 0;
    	for(int i = 1; i <= (int)v.size(); ++i){
    		int mx = 0;
    		for(auto j : v) mx = max(mx, a[j][i]);
    		ret += mx;
    	}
    	return ret;
    }
     
    int main()
    {
    	scanf("%d%d%d", &n, &k, &c);
    	for(int i = 1; i <= n; ++i) for(int j = 1; j <= k; ++j) scanf("%d", &a[i][j]);
    	set < pair < int, vector <int> > > s;
    	s.insert({0, {}});
    	for(int turn = 1; turn <= k; ++turn){
    		set < pair < int, vector <int> > > to;
    		for(auto i : s){
    			for(int j = 1; j <= n; ++j) if(valid(i.S, j)) {
    				vector <int> tmp = i.S; tmp.pb(j);
    				sort(all(tmp));
    				to.insert({val(tmp), tmp});
    			}
    			while((int)to.size() > c + 200) to.erase(to.begin());
    		}
    		s = to;
    	}
    	vector <int> ans;
    	for(auto i : s) ans.pb(i.F);
    	printf("%d\n", ans[s.size() - c]);
    	return 0;
    }

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:34:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |      scanf("%d%d%d", &n, &k, &c);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:35:67: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |      for(int i = 1; i <= n; ++i) for(int j = 1; j <= k; ++j) scanf("%d", &a[i][j]);
      |                                                              ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1752 KB Output is correct
2 Correct 81 ms 1752 KB Output is correct
3 Correct 83 ms 1752 KB Output is correct
4 Correct 76 ms 1744 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 844 KB Output is correct
2 Correct 89 ms 844 KB Output is correct
3 Correct 86 ms 832 KB Output is correct
4 Correct 95 ms 844 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1511 ms 1876 KB Output is correct
2 Correct 1534 ms 1920 KB Output is correct
3 Correct 1581 ms 1800 KB Output is correct
4 Correct 1578 ms 1800 KB Output is correct
5 Correct 1549 ms 1800 KB Output is correct
6 Correct 44 ms 752 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1752 KB Output is correct
2 Correct 81 ms 1752 KB Output is correct
3 Correct 83 ms 1752 KB Output is correct
4 Correct 76 ms 1744 KB Output is correct
5 Correct 89 ms 844 KB Output is correct
6 Correct 89 ms 844 KB Output is correct
7 Correct 86 ms 832 KB Output is correct
8 Correct 95 ms 844 KB Output is correct
9 Correct 1511 ms 1876 KB Output is correct
10 Correct 1534 ms 1920 KB Output is correct
11 Correct 1581 ms 1800 KB Output is correct
12 Correct 1578 ms 1800 KB Output is correct
13 Correct 1549 ms 1800 KB Output is correct
14 Correct 44 ms 752 KB Output is correct
15 Correct 1550 ms 1800 KB Output is correct
16 Correct 1509 ms 1860 KB Output is correct
17 Correct 1519 ms 1888 KB Output is correct
18 Correct 1538 ms 1820 KB Output is correct
19 Correct 1537 ms 1832 KB Output is correct