oj.uz

Submission #231241

# Submission time Handle Problem Language Result Execution time Memory
231241 2020-05-13T06:13:17 Z mohamedsobhi777 Mountains (IOI17_mountains) C++14
20 / 100
 169 ms 384 KB 
/*
        Pure bruteforce
*/
#include "mountains.h"
#include <bits/stdc++.h>

using namespace std ; 

int maximum_deevs(std::vector<int> y) {
        int ret = 0 ; 
        int n = y.size() ; 
        bool gd[n+1][n+1] ; 
        memset(gd , 0 , sizeof gd) ; 
        
        for(int i = 0 ; i < n ;i++){
                for(int j = i+1 ; j< n;j++){
                        for(int k = i+1 ; k < j ;k++){

                                double slp = 1.0 *  (y[i] - y[j]) /( i - j) ;  
                                double o = -1 ; 
                                double c = y[i] - slp * i ; 
                                if(k * slp + y[k] * o + c < 0){
                                        gd[i][j] = gd[j][i] = 1; 
                                }
                                else gd[i][j] = gd[j][i] = 0 ; 
                                                           
                        }
                }
        }

        for(int i = 1 ; i < (1<<n) ; i++){
                vector<pair<int , int> > prs ; 
                for(int j = 0 ;j < n ;j++){
                        if(i &(1<<j)){
                                prs.push_back({j , y[j]}) ; 
                        }
                }
                if(prs.size() < ret) continue ; 
                bool okk = 1 ; 
                for(int j = 0 ; j < prs.size() ; j++){
                        for(int k = j +1 ; k < prs.size() && k < j+2; k++){
                                bool ok = gd[prs[j].first][prs[k].first] ; 
                                if(!ok){
                                        okk = 0 ;
                                        j = prs.size() ;  
                                        break ; 
                                }
                        }
                }
                if(okk){
                        ret = max(ret , (int) prs.size()) ; 
                }
        }

	return ret;
}

Compilation message

mountains.cpp: In function 'int maximum_deevs(std::vector<int>)':
mountains.cpp:38:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(prs.size() < ret) continue ; 
                    ~~~~~~~~~~~^~~~~
mountains.cpp:40:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j = 0 ; j < prs.size() ; j++){
                                 ~~^~~~~~~~~~~~
mountains.cpp:41:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for(int k = j +1 ; k < prs.size() && k < j+2; k++){
                                            ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 162 ms 256 KB Output is correct
7 Correct 164 ms 376 KB Output is correct
8 Correct 165 ms 384 KB Output is correct
9 Correct 159 ms 256 KB Output is correct
10 Correct 80 ms 376 KB Output is correct
11 Correct 162 ms 376 KB Output is correct
12 Correct 160 ms 384 KB Output is correct
13 Correct 162 ms 376 KB Output is correct
14 Correct 166 ms 376 KB Output is correct
15 Correct 160 ms 256 KB Output is correct
16 Correct 169 ms 256 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 162 ms 256 KB Output is correct
7 Correct 164 ms 376 KB Output is correct
8 Correct 165 ms 384 KB Output is correct
9 Correct 159 ms 256 KB Output is correct
10 Correct 80 ms 376 KB Output is correct
11 Correct 162 ms 376 KB Output is correct
12 Correct 160 ms 384 KB Output is correct
13 Correct 162 ms 376 KB Output is correct
14 Correct 166 ms 376 KB Output is correct
15 Correct 160 ms 256 KB Output is correct
16 Correct 169 ms 256 KB Output is correct
17 Incorrect 5 ms 256 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 162 ms 256 KB Output is correct
7 Correct 164 ms 376 KB Output is correct
8 Correct 165 ms 384 KB Output is correct
9 Correct 159 ms 256 KB Output is correct
10 Correct 80 ms 376 KB Output is correct
11 Correct 162 ms 376 KB Output is correct
12 Correct 160 ms 384 KB Output is correct
13 Correct 162 ms 376 KB Output is correct
14 Correct 166 ms 376 KB Output is correct
15 Correct 160 ms 256 KB Output is correct
16 Correct 169 ms 256 KB Output is correct
17 Incorrect 5 ms 256 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 162 ms 256 KB Output is correct
7 Correct 164 ms 376 KB Output is correct
8 Correct 165 ms 384 KB Output is correct
9 Correct 159 ms 256 KB Output is correct
10 Correct 80 ms 376 KB Output is correct
11 Correct 162 ms 376 KB Output is correct
12 Correct 160 ms 384 KB Output is correct
13 Correct 162 ms 376 KB Output is correct
14 Correct 166 ms 376 KB Output is correct
15 Correct 160 ms 256 KB Output is correct
16 Correct 169 ms 256 KB Output is correct
17 Incorrect 5 ms 256 KB Output isn't correct
18 Halted 0 ms 0 KB -