oj.uz

Submission #231234

# Submission time Handle Problem Language Result Execution time Memory
231234 2020-05-13T05:56:23 Z mohamedsobhi777 Mountains (IOI17_mountains) C++14
20 / 100
 206 ms 504 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() ; 

        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++){
                                bool ok = 0 ;
                                double slp = 1.0 *  (prs[j].second - prs[k].second) /( prs[j].first - prs[k].first) ;  
                                double o = -1 ; 
                                double c = prs[j].second - slp * prs[j].first ; 
                                for(int l = prs[j].first +1 ; l < prs[k].first ; l++){
                                        if(l * slp + y[l] * o + c < 0){
                                                ok =1 ; 
                                        }
                                }

                                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:20:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(prs.size() < ret) continue ; 
                    ~~~~~~~~~~~^~~~~
mountains.cpp:22:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j = 0 ; j < prs.size() ; j++){
                                 ~~^~~~~~~~~~~~
mountains.cpp:23:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for(int k = j +1 ; k < prs.size() ; 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 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 193 ms 256 KB Output is correct
7 Correct 180 ms 256 KB Output is correct
8 Correct 168 ms 384 KB Output is correct
9 Correct 206 ms 376 KB Output is correct
10 Correct 76 ms 256 KB Output is correct
11 Correct 200 ms 504 KB Output is correct
12 Correct 155 ms 384 KB Output is correct
13 Correct 180 ms 376 KB Output is correct
14 Correct 176 ms 256 KB Output is correct
15 Correct 179 ms 384 KB Output is correct
16 Correct 162 ms 384 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 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 193 ms 256 KB Output is correct
7 Correct 180 ms 256 KB Output is correct
8 Correct 168 ms 384 KB Output is correct
9 Correct 206 ms 376 KB Output is correct
10 Correct 76 ms 256 KB Output is correct
11 Correct 200 ms 504 KB Output is correct
12 Correct 155 ms 384 KB Output is correct
13 Correct 180 ms 376 KB Output is correct
14 Correct 176 ms 256 KB Output is correct
15 Correct 179 ms 384 KB Output is correct
16 Correct 162 ms 384 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 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 193 ms 256 KB Output is correct
7 Correct 180 ms 256 KB Output is correct
8 Correct 168 ms 384 KB Output is correct
9 Correct 206 ms 376 KB Output is correct
10 Correct 76 ms 256 KB Output is correct
11 Correct 200 ms 504 KB Output is correct
12 Correct 155 ms 384 KB Output is correct
13 Correct 180 ms 376 KB Output is correct
14 Correct 176 ms 256 KB Output is correct
15 Correct 179 ms 384 KB Output is correct
16 Correct 162 ms 384 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 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 193 ms 256 KB Output is correct
7 Correct 180 ms 256 KB Output is correct
8 Correct 168 ms 384 KB Output is correct
9 Correct 206 ms 376 KB Output is correct
10 Correct 76 ms 256 KB Output is correct
11 Correct 200 ms 504 KB Output is correct
12 Correct 155 ms 384 KB Output is correct
13 Correct 180 ms 376 KB Output is correct
14 Correct 176 ms 256 KB Output is correct
15 Correct 179 ms 384 KB Output is correct
16 Correct 162 ms 384 KB Output is correct
17 Incorrect 5 ms 256 KB Output isn't correct
18 Halted 0 ms 0 KB -